On P versus NPco-NP for decision trees and read-once branching programs

DOI10.1007/S000370050005MaRDI QIDQ1587348zbMATH OpenOpenAlexFDO

Authors Stasys Jukna, Alexander Razborov, Petr Savický, Ingo Wegener

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

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1361490
• On the read-once property of branching programs and CNFs of bounded treewidth
• scientific article; zbMATH DE number 7650825
• On Tseitin formulas, read-once branching programs and treewidth
• On Tseitin formulas, read-once branching programs and treewidth
• scientific article; zbMATH DE number 4007722
• On the complexity of branching programs and decision trees for clique functions
• No small nondeterministic read-once branching programs for CNFs of bounded treewidth
• On directional vs. general randomized decision tree complexity for read-once formulas
• On BPP versus \(NP\cup coNP\) for ordered read-once branching programs

Cited in

(15)

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

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

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