Matches in DBpedia 2014 for { <http://dbpedia.org/resource/(SAT,_ε-UNSAT)> ?p ?o. }
Showing items 1 to 10 of
10
with 100 items per page.
- (SAT,_ε-UNSAT) abstract "In computational complexity theory, (SAT, ε-UNSAT) is a language that is used in the proof of the PCP theorem, which relates the language NP to probabilistically checkable proof systems.For a given 3-CNF formula, Φ, and a constant, ε < 1, Φ is in (SAT, ε-UNSAT) if it is satisfiable and not in (SAT, ε-UNSAT) if the maximum number of satisfiable clauses (MAX-3SAT) is less than or equal to (1-ε) times the number of clauses in Φ. If neither of these conditions are true, the membership of Φ in (SAT, ε-UNSAT) is undefined.".
- (SAT,_ε-UNSAT) wikiPageID "3209114".
- (SAT,_ε-UNSAT) wikiPageRevisionID "534592289".
- (SAT,_ε-UNSAT) subject Category:NP-complete_problems.
- (SAT,_ε-UNSAT) comment "In computational complexity theory, (SAT, ε-UNSAT) is a language that is used in the proof of the PCP theorem, which relates the language NP to probabilistically checkable proof systems.For a given 3-CNF formula, Φ, and a constant, ε < 1, Φ is in (SAT, ε-UNSAT) if it is satisfiable and not in (SAT, ε-UNSAT) if the maximum number of satisfiable clauses (MAX-3SAT) is less than or equal to (1-ε) times the number of clauses in Φ.".
- (SAT,_ε-UNSAT) label "(SAT, ε-UNSAT)".
- (SAT,_ε-UNSAT) sameAs (SAT,_%CE%B5-UNSAT).
- (SAT,_ε-UNSAT) sameAs Q4544863.
- (SAT,_ε-UNSAT) sameAs Q4544863.
- (SAT,_ε-UNSAT) wasDerivedFrom (SAT,_ε-UNSAT)?oldid=534592289.