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

DOI10.1007/S000370050005zbMATH Open0962.68075OpenAlexW2619938522MaRDI QIDQ1587348FDOQ1587348

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

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

zbMATH Keywords

computational complexitydecision treesBoolean functionbranching programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (15)

• 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
• Title not available (Why is that?)
• 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
• Computing majority by constant depth majority circuits with low fan-in gates

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)