Pages that link to "Item:Q3546306"
From MaRDI portal
The following pages link to An improved exponential-time algorithm for <i>k</i> -SAT (Q3546306):
Displayed 50 items.
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis (Q354655) (← links)
- Towards NP-P via proof complexity and search (Q408544) (← links)
- Local search for Boolean satisfiability with configuration checking and subscore (Q490437) (← links)
- Algorithms for four variants of the exact satisfiability problem (Q596105) (← links)
- A randomized algorithm for 3-SAT (Q626900) (← links)
- Analysis of local search landscapes for \(k\)-SAT instances (Q626907) (← links)
- An exact algorithm for the Boolean connectivity problem for \(k\)-CNF (Q638525) (← links)
- A comparative runtime analysis of heuristic algorithms for satisfiability problems (Q835804) (← links)
- The complexity of depth-3 circuits computing symmetric Boolean functions (Q845823) (← links)
- Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis (Q894453) (← links)
- On the structure and the number of prime implicants of 2-\(\mathsf{CNF}\)s (Q906424) (← links)
- Computing branchwidth via efficient triangulations and blocks (Q967315) (← links)
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. (Q1408377) (← links)
- Worst-case study of local search for MAX-\(k\)-SAT. (Q1408379) (← links)
- Which problems have strongly exponential complexity? (Q1604206) (← links)
- Local reduction (Q1641001) (← links)
- Matrix rigidity of random Toeplitz matrices (Q1653338) (← links)
- Prediction from partial information and hindsight, an alternative proof (Q1751431) (← links)
- UnitWalk: A new SAT solver that uses local search guided by unit clause elimination (Q1777395) (← links)
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. (Q1853552) (← links)
- On the exact complexity of evaluating quantified \(k\)-\textsc{cnf} (Q1949746) (← links)
- A note on the fine-grained complexity of MIS on regular graphs (Q2032165) (← links)
- A \#SAT algorithm for small constant-depth circuits with PTF gates (Q2118395) (← links)
- Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms (Q2192064) (← links)
- On the complexity of unique circuit SAT (Q2202678) (← links)
- The Boolean satisfiability problem in Clifford algebra (Q2317865) (← links)
- Strong ETH and resolution via games and the multiplicity of strategies (Q2408195) (← links)
- Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT (Q2450932) (← links)
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs (Q2475410) (← links)
- On extremal \(k\)-CNF formulas (Q2509734) (← links)
- On converting CNF to DNF (Q2576880) (← links)
- A new algorithm for optimal 2-constraint satisfaction and its implications (Q2581276) (← links)
- Exploiting partial knowledge of satisfying assignments (Q2643304) (← links)
- (Q2857316) (← links)
- Satisfiability Certificates Verifiable in Subexponential Time (Q3007671) (← links)
- On the Exact Complexity of Evaluating Quantified k-CNF (Q3058691) (← links)
- Local Reductions (Q3448833) (← links)
- Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences (Q3637160) (← links)
- The Complexity of Satisfiability of Small Depth Circuits (Q3656852) (← links)
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture (Q4571929) (← links)
- What Circuit Classes Can Be Learned with Non-Trivial Savings? (Q4638080) (← links)
- (Q5002674) (← links)
- Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT (Q5002768) (← links)
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities (Q5009785) (← links)
- (Q5028438) (← links)
- (Q5090378) (← links)
- Super strong ETH is true for PPSZ with small resolution width (Q5092450) (← links)
- (Q5092465) (← links)
- Walksat Stalls Well Below Satisfiability (Q5267998) (← links)
- Absorbing random walks and the NAE2SAT problem (Q5391499) (← links)