Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable (Q1765303)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable |
scientific article; zbMATH DE number 2137325
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable |
scientific article; zbMATH DE number 2137325 |
Statements
Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable (English)
0 references
23 February 2005
0 references
SAT problem
0 references
Minimal unsatisfiability
0 references
Fixed-parameter complexity
0 references
\(D^P\)-complete problem
0 references
Tree-width
0 references
Bipartite matching
0 references
Expansion
0 references
0 references
0 references
0.9798240661621094
0 references
0.8821298480033875
0 references
0.8396470546722412
0 references
0.8322676420211792
0 references
0.8299187421798706
0 references
