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

DOI10.1007/BFB0029975MaRDI QIDQ4699308zbMATH OpenFDO

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

Publication date 10 November 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Boolean function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• A simple function that requires exponential size read-once branching programs
• A very simple function that requires exponential size read-once branching programs.
• scientific article; zbMATH DE number 1283990

Cited in

(7)

• On P versus NP\(\cap\)co-NP for decision trees and 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\).
• Circuit and decision tree complexity of some number theoretic problems
• A very simple function that requires exponential size read-once branching programs.
• A simple function that requires exponential size read-once branching programs
• scientific article; zbMATH DE number 7650825 (Why is no real title available?)
• On BPP versus \(\text{NP}\cup \text{coNP}\) for ordered read-once branching programs

This page was built for publication: On P versus \(\text{NP}\cap co-\text{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 Q4699308)