scientific article; zbMATH DE number 2080216
From MaRDI portal
Publication:4472459
zbMath1044.03541MaRDI QIDQ4472459
Jochen Messner, Johannes Köbler
Publication date: 4 August 2004
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/1974/19740361.htm
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (6)
Reductions between disjoint NP-pairs ⋮ Speedup for natural problems and noncomputability ⋮ On an optimal randomized acceptor for graph nonisomorphism ⋮ Further oracles separating conjectures about incompleteness in the finite domain ⋮ An oracle separating conjectures about incompleteness in the finite domain ⋮ P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
This page was built for publication:
