Some connections between bounded query classes and non-uniform complexity. (Q1426008): Difference between revisions

From MaRDI portal
← Older edit
Added link to MaRDI item.
Set OpenAlex properties.
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quasi-linear truth-table reductions to \(p\)-selective sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some connections between bounded query classes and non-uniform complexity. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial terse sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: The polynomial-time hierarchy and sparse oracles / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sparse Sets, Lowness and Highness / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4259996 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounded queries to SAT and the Boolean hierarchy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Terse, superterse, and verbose sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of ODD<sub><i>n</i></sub><sup><i>A</i></sup> / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximable sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quantifying the amount of verboseness / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3097395 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The global power of additional queries to random oracles / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Sets Truth-Table Reducible to Sparse Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4385519 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Two queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Lower bounds for constant-depth circuits in the presence of help bits / rank
 
Normal rank
Property / cites work
 
Property / cites work: Enumerative counting is hard / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on enumerative counting / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Structure of Bounded Queries to Arbitrary NP Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4852904 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounded queries in recursion theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: Using self-reducibilities to characterize polynomial time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4251058 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal advice / rank
 
Normal rank
Property / cites work
 
Property / cites work: Theory of semi-feasible algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4281521 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3957950 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On self-reducibility and weak P-selectivity / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of optimization problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: A proof of Beigel's cardinality conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3329452 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Global Power of Additional Queries to<i>P</i>-Random Oracles / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial-Time Membership Comparable Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: A cardinality version of Beigel's nonspeedup theorem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5573961 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A low and a high hierarchy within NP / rank
 
Normal rank
Property / cites work
 
Property / cites work: Probabilistic complexity classes and lowness / rank
 
Normal rank
Property / cites work
 
Property / cites work: Analogues of semirecursive sets and effective reducibilities to the study of NP complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: On membership comparable sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Recursively enumerable sets and degrees / rank
 
Normal rank
Property / cites work
 
Property / cites work: The polynomial-time hierarchy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4131648 / rank
 
Normal rank
Property / cites work
 
Property / cites work: PP is as Hard as the Polynomial-Time Hierarchy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P / rank
 
Normal rank
Property / cites work
 
Property / cites work: Relativized circuit complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complete sets and the polynomial-time hierarchy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some consequences of non-uniform conditions on uniform classes / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/s0890-5401(03)00091-9 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1986637231 / rank
 
Normal rank

Latest revision as of 10:08, 30 July 2024

scientific article
Language Label Description Also known as
English
Some connections between bounded query classes and non-uniform complexity.
scientific article

    Statements

    title
    Some connections between bounded query classes and non-uniform complexity. (English)
    0 references
    author
    Amihood Amir
    0 references
    Richard Beigel
    0 references
    William I. Gasarch
    0 references
    publication date
    14 March 2004
    0 references
    cites work
    Polynomial terse sets
    0 references
    Q4259996
    0 references
    Approximable sets
    0 references
    Q3097395
    0 references
    Q4385519
    0 references
    Two queries
    0 references
    Q4198056
    0 references
    Q4852904
    0 references
    Q4251058
    0 references
    Optimal advice
    0 references
    Q4281521
    0 references
    Q3957950
    0 references
    Q3329452
    0 references
    Q5573961
    0 references
    Q4131648
    0 references

    Identifiers

    zbMATH DE Number
    2056454
    0 references
    OpenAlex ID
    W1986637231
    0 references
     
    Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q1426008&oldid=37219956"
    Powered by MediaWiki