Why combined decision problems are often intractable

DOI10.1007/10720084_15MaRDI QIDQ4518872zbMATH OpenFDO

Authors K. U. Schulz

Publication date 5 June 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/10720084_15

zbMATH Keywords

automated deductioncombined decision proceduresfirst-order theories

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 703132
• scientific article; zbMATH DE number 17813
• scientific article; zbMATH DE number 4010233
• Combination techniques and decision problems for disunification
• Combination techniques and decision problems for disunification
• Decision-theoretic troubleshooting: hardness of approximation
• Multiple-choice decision making by multicriteria combinatorial optimization
• Decision problems, complexity, traces, and representations
• On equivariance and the compound decision problem

Cited in

(4)

• Unions of non-disjoint theories and combinations of satisfiability procedures
• Tractable combinations of theories via sampling
• On the complexity of the partner units decision problem
• Tractable combinations of temporal CSPs

This page was built for publication: Why combined decision problems are often intractable

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