NDLI: The decision problem for the probabilities of higher-order properties

Please wait, while we are loading the content...

Matrix multiplication via arithmetic progressions

Solving minimum-cost flow problems by successive approximation

A new approach to all pairs shortest paths in planar graphs

An algorithm for linear programming which requires $O(((m+n)n^{2}+(m+n)^{1.5}n)L)$ arithmetic operations

A Linear time algorithm for computing the Voronoi diagram of a convex polygon

Testing for cycles in infinite graphs with periodic structure

Approximation algorithms for shortest path motion planning

The complexity of cutting convex polytypes

Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Optimal bounds for decision problems on the CRCW PRAM

Two tapes are better than one for off-line Turing machines

Finite monoids and the fine structure of $NC^{1}$

The strong exponential hierarchy collapses

The Boolean formula value problem is in ALOGTIME

Deterministic simulation in LOGSPACE

Properties that characterize LOGCFL

Some consequences of the existence of pseudorandom generators

Efficiency considerations in using semi-random sources

Imperfect random sources and discrete controlled processes

The power of randomness for communication complexity

Towards a theory of software protection and simulation by oblivious RAMs

On hiding information from an oracle

The complexity of perfect zero-knowledge

Zero knowledge proofs of identity

How to play ANY mental game

Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems

Analysis of backoff protocols for multiple access channels

Dynamic parallel complexity of computational circuits

Constructing disjoint paths on expander graphs

Reconfiguring a hypercube in the presence of faults

On the learnability of Boolean formulae

On learning Boolean functions

A model for hierarchical memory

Parallel symmetry-breaking in sparse graphs

A random NC algorithm for depth first search

A new graphy triconnectivity algorithm and its parallelization

Matching is as easy as matrix inversion

Fast parallel algorithms for chordal graphs

Two algorithms for maintaining order in a list

An optimal online algorithm for metrical task systems

Searching a two key table under a single key

The page number of genus g graphs is (g)

Simple algebras are difficult

Permutation groups in NC

Threshold spectra for random graphs

The decision problem for the probabilities of higher-order properties

Size-time complexity of Boolean networks for prefix computations

Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials

Realistic analysis of some randomized algorithms

Recognizing primes in random polynomial time

The decision problem for the probabilities of higher-order properties

Content Provider	ACM Digital Library
Author	Vardi, M. Kolaitis, P.
Abstract	The probability of a property on the class of all finite relational structures is the limit as n → ∞ of the fraction of structures with n elements satisfying the property, provided the limit exists. It is known that 0-1 laws hold for any property expressible in first-order logic or in fixpoint logic, i.e. the probability of any such property exists and is either 0 or 1. It is also known that the associated decision problem for the probabilities is PSPACE-complete and EXPTIME-complete for first-order logic and fixpoint logic respectively. The 0-1 law fails, however, in general for second-order properties and the decision problem becomes unsolvable.We investigate here logics which on the one hand go beyond fixpoint in terms of expressive power and on the other possess the 0-1 law. We consider first iterative logic which is obtained from first order logic by adding while looping as a construct. We show that the 0-1 law holds for this logic and determine the complexity of the associated decision problem. After this we study a fragment of second order logic called strict &Sgr;11. This class of properties is obtained by restricting appropriately the first-order part of existential second-order sentences. Every strict &Sgr;11 property is NP-computable and there are strict &Sgr;11 properties that are NP-complete, such as 3-colorability. We show that the 0-1 law holds for strict &Sgr;11 properties and establish that the associated decision problem is NEXPTIME-complete. The proofs of the decidability and complexity results require certain combinatorial machinery, namely generalizations of Ramsey's Theorem.
Starting Page	425
Ending Page	435
Page Count	11
File Format	PDF
ISBN	0897912217
DOI	10.1145/28395.28441
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1987-01-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Decision-making with interval probabilities

The Diagonal Problem for Higher-Order Recursion Schemes is Decidable

Solution for the Investment Decision Making Problem through Interval Probabilities

The multiple variable order problem for binary decision diagrams: theory and practical application

Asymptomatic conditional probabilities for first-order logic

On the Estimation of the Second Order Parameter for Heavy-Tailed Distributions

Qualitative properties of solutions of the Neumann problem for a higher-order quasilinear parabolic equation

Distributionally robust chance-constrained Markov decision processes with random transition probabilities

Generalised Risk Constraints in Decision Trees with Second-Order Probabilities

The decision problem for the probabilities of higher-order properties

Similar Documents

Decision-making with interval probabilities

The Diagonal Problem for Higher-Order Recursion Schemes is Decidable

Solution for the Investment Decision Making Problem through Interval Probabilities

The multiple variable order problem for binary decision diagrams: theory and practical application

Asymptomatic conditional probabilities for first-order logic

On the Estimation of the Second Order Parameter for Heavy-Tailed Distributions

Qualitative properties of solutions of the Neumann problem for a higher-order quasilinear parabolic equation

Distributionally robust chance-constrained Markov decision processes with random transition probabilities

Generalised Risk Constraints in Decision Trees with Second-Order Probabilities

The decision problem for the probabilities of higher-order properties