scientific article; zbMATH DE number 1361490

zbMATH Open0941.68062MaRDI QIDQ4699308FDOQ4699308

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

Publication date: 10 November 1999

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

Boolean function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (7)

• Circuit and decision tree complexity of some number theoretic problems
• 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
• A very simple function that requires exponential size read-once branching programs.
• Title not available (Why is that?)
• On BPP versus \(NP\cup coNP\) for ordered read-once branching programs
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs

This page was built for publication:

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