Questions tagged [proof-complexity]

propositional proof systems and corresponding bounded arithmetic theories

Filter by
Sorted by
Tagged with
0 votes
0 answers
94 views

On the polynomial-size Frege proof of the propositional pigeonhole principle

I'm reading a lecture note on the proof of PHP, which mentioned that a "basic fact" $$ \left(\sum\limits_{i=1}^{s-1} A_i\ge a\right) \land A_s \to \sum\limits_{i=1}^s A_i\ge a $$ is ...
Soha's user avatar
  • 187
3 votes
1 answer
201 views

Horn clause on cnf

Recall that a CNF formula is Horn if each clause contains at most one positive literal. Is it possible any unsatisfiable Horn CNF formula has a polynomial-size treelike Resolution refutation? Is there ...
Brett's user avatar
  • 33
4 votes
0 answers
56 views

Complexity of circuit evaluation in Resolution

Consider the standard evaluation function for CNF formulas $\mathsf{Eval}(\varphi,x)$ taking as input a CNF $\varphi$ and an assignment $x$ to the variables and outputting the value of $\varphi(x)$. ...
Noel Arteche's user avatar
4 votes
1 answer
205 views

A variation of propositional pigeonhole principle

Let $n$ be the number of pigeons, and $x_{i,j}$ denote the Boolean variable indicating that pigeon #$i$ is mapped to hole #$j$. Then the propositional pigeonhole principle (PHP) is the conjunction of ...
Soha's user avatar
  • 187
5 votes
2 answers
241 views

Can CDCL Algorithm Derived Conflict Clauses Always Be Obtained Through Resolution from an Unsatisfiable CNF Formula?

I have a question regarding the Conflict-Driven Clause Learning (CDCL) algorithm applied to an unsatisfiable CNF formula $F$. Specifically, can all the conflict clauses learned by the CDCL algorithm ...
Jxb's user avatar
  • 316
4 votes
2 answers
554 views

Do we currently know a polynomial-size Frege proof for Tseitin formulas?

There's a vast literature about super-polynomial lower bounds on proof lengths of Tseitin formulas in bounded-depth Frege systems, but what I'm curious about is: what if we don't restrict the depth of ...
Soha's user avatar
  • 187
4 votes
1 answer
104 views

Power of non-implicationally-complete Frege systems and Boolean equational calculus

We know that Frege systems are required to be implicationally complete -- namely, if a set of formulas $B_1,B_2,\cdots,B_t$ imply formula $C$, then this implication can be proven in the system. I'm ...
Soha's user avatar
  • 187
4 votes
1 answer
92 views

Methods for Determining the minimal Width of Resolution Refutations for CNF Formulas

Recall that the width of a resolution refutation $R$ of a CNF formula $F$ is the maximal number of literals in any clause occurring in $R$. I am intersting in finding the minimal width of some certain ...
Jxb's user avatar
  • 316
2 votes
0 answers
73 views

Proof systems that may be stronger than extended Frege?

The extended Frege proof system is thought to be a fairly strong proof system, with no known superpolynomial lower bounds. But I wonder, if extended Frege is proved not to be polynomially bounded one ...
Soha's user avatar
  • 187
1 vote
0 answers
62 views

Automatizability of Extended Resolution

According to Krajícek, Jan and Pavel Pudlák. “Some Consequences of Cryptographical Conjectures for S12 and EF.” Inf. Comput. 140 (1998): 82-94., the extended Frege proof system is not automatizable ...
Soha's user avatar
  • 187
3 votes
0 answers
75 views

How does extended resolution p-simulate extended Frege?

I found a slide stating that "extended resolution and extended Frege p-simulate each other", without providing a proof. It's obvious that extended Frege p-simulates extended resolution, but ...
Soha's user avatar
  • 187
0 votes
0 answers
119 views

When the tree-like resolution size is the same with general(regular) resolution size?

Background: For an unsatisfiable SAT formulas, the length of a resolution refutaion means the number of clauses in it. It's well known that there exist exponential separation between tree-like and ...
Jxb's user avatar
  • 316
1 vote
0 answers
75 views

Do soundness and completeness need to be exact converses of eachother?

This question concerns the derivational soundness and completeness of the first-order proof system LK (without equality) as presented in Logical Foundations of Proof Complexity by Cook and Nguyen. In ...
Johnny's user avatar
  • 201
1 vote
1 answer
78 views

Why isn't the proof obtained using Buss's proof of the derivational completeness of LK anchored?

The version of Buss's proof I'm referring to is the proof of Lemma II.2.24 in Logical Foundations of Proof Complexity by Cook and Nguyen. In the interest of keeping this question self-contained I've ...
Johnny's user avatar
  • 201
0 votes
0 answers
157 views

What's the connection between branchwidth and treewidth

I understand that treewidth and branchwidth are essentially equivalent for a fixed graph, given that $branchwidth(G) = Θ(treewidth(G))$. However, my question pertains to a specific case involving ...
Jxb's user avatar
  • 316
14 votes
2 answers
2k views

Algebraic equivalent of SAT?

Starting with a simple observation. If $x,y\in\{0,1\}$, then the arithmetic product $x\cdot y$ corresponds to the logical conjunction if we interpret $1$ as true and $0$ as false. But then, for a ...
Nicola Gigante's user avatar
4 votes
1 answer
141 views

Is there a relation between the techniques used by Dan Willard, versus those of Brown and Palsberg, to exclude diagonalization?

This question extends my inquiry from a previous post [0]. Dan Willard's Self-Justifying Axiom Systems/Self-Verifying Theories [1] and Brown and Palsberg's self-interpreter for F-Omega [2] both employ ...
jpt4's user avatar
  • 81
0 votes
0 answers
130 views

Boolean logic: What is the name of this trick to replace explicit negations by implications?

Consider a Boolean circuit $C$ composed of some finite set of input variables $A_1,\ldots, A_n$ and the connectives $\lor\land\neg\rightarrow$ (with $X\rightarrow Y=\neg X\lor Y$) (update: assume that ...
Duyal Yolcu's user avatar
7 votes
0 answers
102 views

Algorithmically determining proof complexity for Frege systems?

I apologize if this falls wildly short of research level - I am just learning the very basics of proof complexity and lack any real logic background. Let $F$ be a Frege proof system (a finite complete ...
Sprotte's user avatar
  • 171
3 votes
1 answer
272 views

Proof of SPFA's worst-case complexity?

I am trying to prove the worst-case asymptotic time complexity of the Shortest Path Faster Algorithm (SPFA). I know the complexity is the same as the "original" Bellman-Ford (BF) algorithm, ...
Maltus's user avatar
  • 73
9 votes
0 answers
417 views

Examples of simulations in proof complexity that are not p-simulations

I am writing a paper on the complexity of some unorthodox proof systems, where I have two systems $P$ and $Q$ such that $P$ simulates $Q$ in the sense of it being possible to translate a $Q$-proof ...
Emre Yolcu's user avatar
2 votes
0 answers
122 views

Asymptotic complexity lower bounds of proof checking

This paper on universal search mentions (on pp. 6-7) that proof checking can be done in $O(n^2)$ where $n$ is the length of the proof. Is this optimal? I don't want to specify the problem too ...
Mario Carneiro's user avatar
-4 votes
1 answer
223 views

Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
Atsina's user avatar
  • 119
2 votes
0 answers
120 views

Proof systems induced by NP-complete problems

Satisfiability is the fundamental NP-complete problem. Cook-Reckhow theorem states that the existence of a propositional proof system that admits polynomial size proofs for all tautologies implies ...
Mohammad Al-Turkistany's user avatar
3 votes
0 answers
130 views

Have the proofs in Buss's "On Goedel’s Theorems on Lengths of Proofs" been formalized (mechanically checked)?

The paper On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics contains quite interesting results on proof length. But some of the details are still, to me, a bit ...
Jacques Carette's user avatar
7 votes
1 answer
205 views

Document references describing weaknesses for cutting planes and algebraic proof system?

Here, Fortnow says (section 4.3): Since then complexity theorists have shown similar weaknesses in a number of other proof systems including cutting planes, algebraic proof systems based on ...
Jérôme Verstrynge's user avatar
4 votes
1 answer
168 views

Eliminating tautological axioms in tree-like $k$-DNF resolution

The propositional proof system $k$-DNF-resolution, a.k.a. $Res(k)$, is a generalization of propositional resolution, where the lines in a proof are $k$-DNF formulas, i.e., disjunctions of $k$-terms of ...
Jan Johannsen's user avatar
6 votes
1 answer
125 views

Axioms of Minimum Size Resolution Refutations

Let $\phi$ be an unsatisfiable CNF formula and let $\Pi$ be a resolution refutation of $\phi$ of minimum size. Let $\psi$ be the subformula of $\phi$ containing the clauses that actually appear as ...
Nathan's user avatar
  • 243
4 votes
0 answers
250 views

Testing emptiness property complexity in Sum of Squares Proof systems

Take the set $$\mathcal T=\{f_1(x_1,\dots,x_n)=\dots=f_m(x_1,\dots,x_n)=0, h_1(x_1,\dots,x_n)\geq a_1,\dots,h_t(x_1,\dots,x_n)\geq a_t\}$$ where $$h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb ...
VS.'s user avatar
  • 539
0 votes
1 answer
62 views

Understanding the definition of a "restriction of a resolution derivation"

I am reading the paper An Introduction to Lower Bounds on Resolution Proof Systems. In its subsection 2.3 the author gives an inductive definition of the restriction of a resolution refutation $\pi$. ...
RTK's user avatar
  • 311
3 votes
0 answers
65 views

Efficient transformation of clausal proof into resolution proof

Clausal proof is used to certify unsat results of SAT solvers. However the main theoretical results are on resolution proof (for instance, the non existence of a polynomial resolution proof for the ...
RTK's user avatar
  • 311
3 votes
0 answers
137 views

Transforming a DAG-like resolution proof to a tree like resolution proof

How can a DAG-like resolution proof be transformed to a tree-like resolution proof? Is such a transformation possible in polynomial time?
RTK's user avatar
  • 311
5 votes
1 answer
95 views

Resolution augmented with the rule of symmetry or the rule of extension

Krishnamurthy (here is the abstract of his paper) showed that resolution augmented with the principle of symmetry forms a proof system (referred to as SR) in which certain formulas (which do not admit ...
RTK's user avatar
  • 311
6 votes
1 answer
228 views

Resolution vs Nondeterministic Search Problems

It is well known that each resolution refutation $\Pi$ for an unsatisfiable CNF formula $F = C_1\wedge C_2 \wedge ... \wedge C_m$ over variables $X$ can be translated in polynomial time (in the size ...
verifying's user avatar
  • 1,072
2 votes
2 answers
128 views

IPS upper bound for subset sum axiom

I am reading the following paper Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson ,"Proof Complexity Lower Bounds from Algebraic Circuit Complexity", 2016. IPS is defined as follows: ...
Chetan Gupta's user avatar
3 votes
2 answers
145 views

Construct proof systems for common algorithmic task, like equivalence of regular expressions

A propositional proof system according to Cook and Reckhow for a language $L \subseteq \Sigma^{\ast}$ is a deterministic polynomial time function $f : \Sigma^{\ast} \to L$ that is onto. For $y \in L$ ...
StefanH's user avatar
  • 2,077
1 vote
0 answers
149 views

Proof of Correctness of Bottleneck Dijkstra Algorithm [closed]

I am working on a bottleneck multicast tree for which I am using bottleneck Dijkstra algorithm. My question is 1) bottleneck Dijkstra has the same correctness as that of (simple) Dijkstra or not ? 2)...
Ali's user avatar
  • 11
4 votes
1 answer
158 views

Is there any work relating type systems and Cook-Reckhow proof systems?

An important subfield of computational complexity is proof complexity, mostly due to Cook and Reckhow. E.g. one notable result is that a proof system that has efficient proofs (i.e., in length ...
pron's user avatar
  • 175
0 votes
1 answer
288 views

In regards to the tautologies of a polynomially-bounded propositional proof system

In the book 'Logical Foundations of Proof Complexity', co-authored by Stephen Cook, the following definition is given: A proof-system $F$ is said to be polynomially-bounded if there is a polynomial p(...
Boolean_functions's user avatar
10 votes
1 answer
405 views

Lower Bounds for Frege and Extended Frege

Wikipedia [1] states that the best known lower bound for size of Frege proofs is quadratic, and that there is no known superlinear lower bounds for the number of lines of Frege proofs. Questions: 1)...
verifying's user avatar
  • 1,072
-1 votes
1 answer
125 views

On the difference between propositional proof system and polynomially-bounded proof system

For the definition of a propositional proof system we have: An abstract proof system is a polynomial time function f whose range is equal to the set of tautologies. If τ is a tautology, then an f-...
Boolean_functions's user avatar
-4 votes
1 answer
319 views

NP-completeness of one generalized subset sum problem (target sum belongs to interval) [closed]

I need to prove that decision problem: for a given set of positive integers $a_1, ..., a_n$, does it exist a subset that sums up to a value within interval $[\frac{1}{2}\sum a_i; \frac{1}{2}\sum a_i+...
Alec's user avatar
  • 95
7 votes
2 answers
350 views

Are there any propositional proof systems which are not Cook-Reckhow proof systems?

An abstract proof system is a polynomial time function $f$ whose range is equal to the set of tautologies. If $\tau$ is a tautology, then an $f$-proof of $\tau$ is any value $\pi$ such that $f(\pi) =...
Slacked's user avatar
  • 71
-3 votes
1 answer
84 views

On the (Cook) definition of a propositional proof system [closed]

Def: An abstract proof system is a polynomial time function f whose range is equal to the set of tautologies. If T is a tautology, then an f-proof of T is any value w such that f(w)= T I'm a bit ...
Stacked's user avatar
2 votes
0 answers
123 views

Techniques for showing intermediate status between $\mathsf{NP \cap coNP}$ and coNP-completeness

Inspired by Suresh's post, for a new problem in $\mathsf{coNP}$, whose true proof complexity is intermediate between $\mathsf{NP \cap coNP}$ and being coNP-complete, I am interested in methods which ...
Mohammad Al-Turkistany's user avatar
1 vote
0 answers
155 views

Do problems have to be statable in $\Pi_1$ to use Levin's universal search to find short proofs if P=NP

In If P=NP, could we obtain proofs of Goldbach's Conjecture etc.? it talks about the hypothetical world where P=NP and using the proof of it to prove a problem/theorem assuming that it has a short ...
time's user avatar
  • 21
10 votes
3 answers
413 views

Graph theoretic restriction to Proofs in Proof Complexity Theory

Proof complexity is a most basic area of computational complexity theory. An ultimate purpose of this area is to prove $NP\neq coNP$, that is, any prover cannot give a proof of unsatisfiability of ...
shen's user avatar
  • 101
28 votes
6 answers
1k views

Natural NP-complete problems with "large" witnesses

The question on cstheory "What is NP restricted to linear size witnesses?" asks about the class NP restricted to linear size $O(n)$ witnesses, but Are there natural NP-complete problems in which (...
Marzio De Biasi's user avatar
7 votes
0 answers
206 views

Implications of the impossibility of efficient sampling from random non-Hamiltonian graphs

Nisan's answer to this question shows the Impossiblity of efficient sampling from random non-Hamiltonian graphs (unless $NP=coNP$). I am interested in the implications of this conjecture. Does the ...
Mohammad Al-Turkistany's user avatar
9 votes
1 answer
303 views

Proof complexity and lower bounds

One way to prove NP$\neq$ coNP is to show that for every propositional proof system $f$ computable in polynomial time, there exists a family of tautologies for which $f$ requires super polynomial ...
Karteek's user avatar
  • 93