A satisfiability algorithm and average-case hardness for formulas over the full binary basis (Q354655): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Import241208061232 (talk | contribs)
Normalize DOI.
 
(4 intermediate revisions by 4 users not shown)
Property / DOI
 
Property / DOI: 10.1007/s00037-013-0067-7 / rank
Normal rank
 
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2104306727 / rank
 
Normal rank
Property / cites work
 
Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank
 
Normal rank
Property / cites work
 
Property / cites work: A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algorithms and Computation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5503674 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the construction of affine extractors / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Complexity of Satisfiability of Small Depth Circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: An improved exponential-time algorithm for <i>k</i> -SAT / rank
 
Normal rank
Property / cites work
 
Property / cites work: STACS 2004 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parity, circuits, and the polynomial-time hierarchy / rank
 
Normal rank
Property / cites work
 
Property / cites work: The effect of random restrictions on formula size / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Shrinkage Exponent of de Morgan Formulas is 2 / rank
 
Normal rank
Property / cites work
 
Property / cites work: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3281059 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5743451 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Hardness against Constant-Depth Linear-Size Circuits / rank
 
Normal rank
Property / cites work
 
Property / cites work: Derandomizing the HSSW algorithm for 3-SAT / rank
 
Normal rank
Property / cites work
 
Property / cites work: Solving satisfiability in less than \(2^ n\) steps / rank
 
Normal rank
Property / cites work
 
Property / cites work: A full derandomization of schöning's k-SAT algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hardness vs randomness / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4484662 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4218095 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An algorithm for the satisfiability problem of formulas in conjunctive normal form / rank
 
Normal rank
Property / cites work
 
Property / cites work: Improving exhaustive search implies superpolynomial lower bounds / rank
 
Normal rank
Property / cites work
 
Property / cites work: Affine extractors over prime fields / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1007/S00037-013-0067-7 / rank
 
Normal rank

Latest revision as of 15:17, 9 December 2024

scientific article
Language Label Description Also known as
English
A satisfiability algorithm and average-case hardness for formulas over the full binary basis
scientific article

    Statements

    A satisfiability algorithm and average-case hardness for formulas over the full binary basis (English)
    0 references
    0 references
    0 references
    19 July 2013
    0 references
    satisfiability
    0 references
    exact algorithm
    0 references
    formula
    0 references
    parity gate
    0 references
    average-case hardness
    0 references

    Identifiers