scientific article; zbMATH DE number 1405671

zbMATH Open0938.03022MaRDI QIDQ4938652FDOQ4938652

Authors: Mario Szegedy 

Publication date: 22 June 2000

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 512858
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• Nearly-linear size holographic proofs
• scientific article; zbMATH DE number 4049622
• scientific article; zbMATH DE number 1754535

zbMATH Keywords

three-valued logicholographic proof checkingrandomized non-deterministic machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Many-valued logic (03B50) Mechanization of proofs and logical operations (03B35)

Cited In (7)

• Combinatorial PCPs with short proofs
• Short locally testable codes and proofs: a survey in two parts
• Fast approximate probabilistically checkable proofs
• Short locally testable codes and proofs
• Combinatorial PCPs with efficient verifiers
• Low-degree test with polynomially small error
• Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4938652)