Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with logic:
TR98-067 | 12th November 1998
Paul Beame

Propositional Proof Complexity: Past, Present and Future

Proof complexity, the study of the lengths of proofs in
propositional logic, is an area of study that is fundamentally connected
both to major open questions of computational complexity theory and
to practical properties of automated theorem provers. In the last
decade, there have been a number of significant advances ... more >>>

TR03-024 | 25th February 2003
Till Tantau

Weak Cardinality Theorems for First-Order Logic

Kummer's cardinality theorem states that a language is recursive
if a Turing machine can exclude for any n words one of the
n + 1 possibilities for the number of words in the language. It
is known that this theorem does not hold for polynomial-time
computations, but there ... more >>>

TR06-021 | 10th February 2006
Tomas Feder

Constraint satisfaction: a personal perspective

Attempts at classifying computational problems as polynomial time
solvable, NP-complete, or belonging to a higher level in the polynomial
hierarchy, face the difficulty of undecidability. These classes, including
NP, admit a logic formulation. By suitably restricting the formulation, one
finds the logic class MMSNP, or monotone monadic strict NP without
more >>>

TR06-160 | 17th December 2006
Tomas Feder, Phokion G. Kolaitis

Closures and dichotomies for quantified constraints

Quantified constraint satisfaction is the generalization of
constraint satisfaction that allows for both universal and existential
quantifiers over constrained variables, instead
of just existential quantifiers.
We study quantified constraint satisfaction problems ${\rm CSP}(Q,S)$, where $Q$ denotes
a pattern of quantifier alternation ending in exists or the set of all possible
more >>>

TR09-111 | 5th November 2009
Walid Gomaa

Model-Theoretic Characterization of Complexity Classes

Model theory is a branch of mathematical logic that investigates the
logical properties of mathematical structures. It has been quite
successfully applied to computational complexity resulting in an
area of research called descriptive complexity theory. Descriptive
complexity is essentially a syntactical characterization of
complexity classes using logical formalisms. However, there ... more >>>

TR11-158 | 25th November 2011
Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin

Locality from Circuit Lower Bounds

We study the locality of an extension of first-order logic that captures graph queries computable in AC$^0$, i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the ... more >>>

TR12-069 | 23rd March 2012
Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry

On the complexity of computing minimal unsatisfiable LTL formulas

We show that (1) the Minimal False QCNF search problem (MF-search) and
the Minimal Unsatisfiable LTL formula search problem (MU-search) are FPSPACE complete because of the very expressive power of QBF/LTL, (2) we extend the PSPACE-hardness of the MF decision problem to the MU decision problem. As a consequence, we ... more >>>

TR15-029 | 18th February 2015
Stanislav Zak

Inherent logic and complexity

Abstract. The old intuitive question "what does the machine think" at
different stages of its computation is examined. Our paper is based on
the formal de nitions and results which are collected in the branching
program theory around the intuitive question "what does the program
know about the contents of ... more >>>

TR16-040 | 16th March 2016
Baris Aydinlioglu, Eric Bach

Affine Relativization: Unifying the Algebrization and Relativization Barriers

Revisions: 1

We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure ... more >>>

ISSN 1433-8092 | Imprint