Results 11 to 20 of about 1,041,680 (279)
Complexity of Semialgebraic Proofs [PDF]
Moscow Mathematical Journal, 2002 Summary: It is a known approach to translate propositional formulas into systems of polynomial inequalities and consider proof systems for the latter. The well-studied proof systems of this type are the Cutting Plane proof system (CP) utilizing linear inequalities and the Lovász-Schrijver calculi (LS) utilizing quadratic inequalities.
Grigoriev, D, Hirsch, E, Pasechnik, D
openaire +6 more sources
Pebble Games, Proof Complexity, and Time-Space Trade-offs [PDF]
Logical Methods in Computer Science, 2013 Pebble games were extensively studied in the 1970s and 1980s in a number of different contexts. The last decade has seen a revival of interest in pebble games coming from the field of proof complexity. Pebbling has proven to be a useful tool for studying
Jakob Nordstrom
doaj +1 more source
Parameterized Proof Complexity [PDF]
computational complexity, 2007 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Dantchev, S., Martin, B., Szeider, S.
openaire +2 more sources
Sublogarithmic uniform Boolean proof nets [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 Using a proofs-as-programs correspondence, Terui was able to compare two models of parallel computation: Boolean circuits and proof nets for multiplicative linear logic. Mogbil et. al.
Clément Aubert
doaj +1 more source
Gravitation from optimized computation: Einstein and beyond
Journal of High Energy Physics, 2023 A new principle in quantum gravity, dubbed spacetime complexity, states that gravitational physics emerges from spacetime seeking to optimize the computational cost of its quantum dynamics.
Rafael Carrasco +3 more
doaj +1 more source
A System of Interaction and Structure III: The Complexity of BV and Pomset Logic [PDF]
Logical Methods in Computer Science, 2023 Pomset logic and BV are both logics that extend multiplicative linear logic (with Mix) with a third connective that is self-dual and non-commutative. Whereas pomset logic originates from the study of coherence spaces and proof nets, BV originates from ...
Lê Thành Dũng Nguyên +1 more
doaj +1 more source
Shielding Probabilistically Checkable Proofs: Zero-Knowledge PCPs from Leakage Resilience
Entropy, 2022 Probabilistically Checkable Proofs (PCPs) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form “x∈L” by querying only a few proof bits.
Mor Weiss
doaj +1 more source
ZKFERP:Universal and Efficient Range Proof Scheme with Constant Computational Cost [PDF]
Jisuanji kexue, 2022 The decentralization of blockchain can easily lead to the leakage of users’ private data at the transaction layer,which in turn leads to information security issues.The zero-knowledge range proof is designed to confidentially verify that the transaction ...
LI Yi-cong, ZHOU Kuan-jiu, WANG Zi-zhong, XU Lin
doaj +1 more source
Perfect Matching in Random Graphs is as Hard as Tseitin [PDF]
TheoretiCS, 2022 We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times.
Per Austrin, Kilian Risse
doaj +1 more source
Polylogarithmic Cuts in Models of V^0 [PDF]
Logical Methods in Computer Science, 2013 We study initial cuts of models of weak two-sorted Bounded Arithmetics with respect to the strength of their theories and show that these theories are stronger than the original one.
Sebastian Müller
doaj +1 more source