On Computation Complexity of True Proof Number Search
- URL: http://arxiv.org/abs/2102.04907v1
- Date: Mon, 8 Feb 2021 06:06:54 GMT
- Title: On Computation Complexity of True Proof Number Search
- Authors: Chao Gao
- Abstract summary: We show that the computation of true emphproof and emphdisproof numbers for proof number search in arbitrary directed acyclic graphs is NP-hard.
The proof requires a reduction from SAT, which demonstrates that finding true proof/disproof number for arbitrary DAG is at least as hard as deciding if arbitrary SAT instance is satisfiable.
- Score: 19.376328966299322
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We point out that the computation of true \emph{proof} and \emph{disproof}
numbers for proof number search in arbitrary directed acyclic graphs is
NP-hard, an important theoretical result for proof number search. The proof
requires a reduction from SAT, which demonstrates that finding true
proof/disproof number for arbitrary DAG is at least as hard as deciding if
arbitrary SAT instance is satisfiable, thus NP-hard.
Related papers
- Unclonable Non-Interactive Zero-Knowledge [13.011345529764787]
A non-interactive ZK (NIZK) proof enables verification of NP statements without revealing secrets about them.
In this paper, we ask whether it is possible to rely on quantum information in order to build NIZK proof systems that are impossible to clone.
arXiv Detail & Related papers (2023-10-11T01:32:36Z) - Optimising T-count is NP-hard [0.0]
We find an upper bound to the T-count problem of $textNPtextNQP$ in a reversible classical circuit.
arXiv Detail & Related papers (2023-09-12T09:35:23Z) - SAT Requires Exhaustive Search [5.859552783895773]
This paper shows that proving computational hardness is not hard in mathematics.
In cases of extremely hard examples, exhaustive search may be the only viable option.
It makes the separation between SAT (with long clauses) and 3-SAT much easier than that between 3-SAT and 2-SAT.
arXiv Detail & Related papers (2023-02-19T09:04:17Z) - Estimating the hardness of SAT encodings for Logical Equivalence
Checking of Boolean circuits [58.83758257568434]
We show that the hardness of SAT encodings for LEC instances can be estimated textitw.r.t some SAT partitioning.
The paper proposes several methods for constructing partitionings, which, when used in practice, allow one to estimate the hardness of SAT encodings for LEC with good accuracy.
arXiv Detail & Related papers (2022-10-04T09:19:13Z) - Connes implies Tsirelson: a simple proof [91.3755431537592]
We show that the Connes embedding problem implies the synchronous Tsirelson conjecture.
We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
arXiv Detail & Related papers (2022-09-16T13:59:42Z) - Who Finds the Short Proof? An Exploration of variants of Boolos' Curious
Inference using Higher-order Automated Theorem Provers [62.997667081978825]
We report on an exploration of variants of Boolos' curious inference using higher-order automated theorem provers.
Surprisingly, only a single shorthand notation still had to be provided by hand.
All higher-order lemmas required for obtaining short proof are automatically discovered by the computer.
arXiv Detail & Related papers (2022-08-14T16:31:04Z) - Generating Natural Language Proofs with Verifier-Guided Search [74.9614610172561]
We present a novel stepwise method NLProofS (Natural Language Proof Search)
NLProofS learns to generate relevant steps conditioning on the hypothesis.
It achieves state-of-the-art performance on EntailmentBank and RuleTaker.
arXiv Detail & Related papers (2022-05-25T02:22:30Z) - Automating Reasoning with Standpoint Logic via Nested Sequents [0.0]
Standpoint logic advocates a multi-perspective approach permitting reasoning with a selection of diverse and possibly conflicting standpoints.
We show how to automate standpoint reasoning by means of non-deterministic proof-search algorithms.
arXiv Detail & Related papers (2022-05-05T16:27:57Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete.
We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes.
Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
arXiv Detail & Related papers (2021-08-10T15:00:20Z) - multiPRover: Generating Multiple Proofs for Improved Interpretability in
Rule Reasoning [73.09791959325204]
We focus on a type of linguistic formal reasoning where the goal is to reason over explicit knowledge in the form of natural language facts and rules.
A recent work, named PRover, performs such reasoning by answering a question and also generating a proof graph that explains the answer.
In our work, we address a new and challenging problem of generating multiple proof graphs for reasoning over natural language rule-bases.
arXiv Detail & Related papers (2021-06-02T17:58:35Z) - The Long, the Short and the Random [0.0]
The algorithm computes the exact counting of satisfying assignments in sub-exponential time.
The algorithm uses a nice property that every CNF formula has, which relates its number of unsatisfying assignments to the space of its monotone sub-formulae.
arXiv Detail & Related papers (2020-11-03T12:00:07Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.