Complete problems in the first-order predicate calculus (Q1075318): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2066989651 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Alternation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5679729 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3919057 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of theorem-proving procedures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4058132 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3862379 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complete problems for deterministic polynomial time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New problems complete for nondeterministic log space / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Turing machines and the spectra of first-order formulas / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity results for classes of quantificational formulas / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity classes and theories of finite models / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4124327 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4140378 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Machine-Oriented Logic Based on the Resolution Principle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5541351 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of propositional linear temporal logics / rank | |||
Normal rank |
Latest revision as of 13:55, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complete problems in the first-order predicate calculus |
scientific article |
Statements
Complete problems in the first-order predicate calculus (English)
0 references
1984
0 references
Neben den klassischen Komplexitätsklassen P und NP wird seit längerem eine Reihe weiterer solcher Klassen untersucht. Der Autor stellt einen Zusammenhang zwischen einigen Formeln der Prädikatenlogik 1. Stufe und Turingmaschinen her. Diese zunächst sehr abstrakte Aussage wird dazu benutzt, eine natürliche Hierarchie vollständiger Probleme für die Klassen P, NP, PSPACE, deterministische und nichtdeterministische exponentielle Zeit, deterministische und nichtdeterministische doppelt exponentielle Zeit, DLOGSPACE und NLOGSPACE zu entwickeln. Eine ähnliche Hierarchie ergibt sich, wenn nach der Existenz von Beweisen einer vorgegebenen maximalen Tiefe für die oben genannten Formeln gefragt wird. Spezielle Resultate betreffen u.a. ein erstes Beispiel eines vollständigen Problems für EXPSPACE. Eine mögliche Anwendung dieser Ergebnisse liegt in der Beschleunigung von Beweisführungsprogrammen.
0 references
Turing machines
0 references
first-order predicate calculus formulae that are
0 references
complete for various complexity classes
0 references
resolution theorem proving
0 references
systems
0 references