scientific article

zbMath0629.68049MaRDI QIDQ3766851

Klaus W. Wagner

Publication date: 1986

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

NP-completenesstruth-table reducibilityBoolean closure of NPBoolean formula reducibilityHausedorf reducibilityTuring recucibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (8)

Polynomial terse sets ⋮ The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) ⋮ Nondeterministic bounded query reducibilities ⋮ On the complexity of input/output logic ⋮ \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP] ⋮ Solving conflicts in information merging by a flexible interpretation of atomic propositions ⋮ \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

This page was built for publication: