On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs

DOI10.1007/s000370050005zbMath0962.68075OpenAlexW2619938522MaRDI QIDQ1587348

Stasys P. Jukna, Ingo Wegener, Alexander A. Razborov, Petr Savický

Publication date: 20 November 2000

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s000370050005

zbMATH Keywords

computational complexitydecision treesBoolean functionbranching programs

Mathematics Subject Classification ID

Related Items (11)

Finding the Median (Obliviously) with Bounded Space ⋮ On (simple) decision tree rank ⋮ Yet harder knapsack problems ⋮ Minimization of decision trees is hard to approximate ⋮ On BPP versus \(NP\cup coNP\) for ordered read-once branching programs ⋮ A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs ⋮ Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\). ⋮ Computing majority by constant depth majority circuits with low fan-in gates ⋮ On the P versus NP intersected with co-NP question in communication complexity ⋮ A hierarchy result for read-once branching programs with restricted parity nondeterminism ⋮ Lower bounds for linearly transformed OBDDs and FBDDs

This page was built for publication: On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs