Comparing the expressibility of two languages formed using NP-complete graph operators

DOI10.1007/3-540-53832-1_49MaRDI QIDQ4028122zbMATH OpenFDO

Authors Iain Stewart

Publication date 28 March 1993

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

Full work available at URL https://doi.org/10.1007/3-540-53832-1_49

zbMATH Keywords

first-order language FONP-complete graph operatorsrepresentation of complexity classes via languages

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

[For the entire collection see Zbl 0747.00042.] We consider extending the first-order language FO by the operator 3COL (corresponding to the problem of deciding whether a graph can be properly coloured using at most 3 colours), and we compare our results with those of \textit{I. A. Stewart} [Using the Hamiltonian path operator to capture NP, Univ. Newcastle upon Tyne Tech. Rep., 1990: to appear in Proc. 2nd International Conference on Computing and Information, Niagara Falls, Canada, Lect. Notes in Computer Science, Springer-Verlag (1989)] concerning the similarly defined language (FO+HP) (where HP is the operator corresponding to the problem of deciding whether there is a Hamiltonian path in a digraph between two distinguished vertices). We see that whereas the problems represented by sentences of (FO+posHP) are exactly those of NP, that is, NP=(FO+posHP), we have that if (FO+pos3COL)=NP, then NP=co-NP (here, (FO+pos3COL) denotes the sub- language of (FO+3COL) where applications of the operator 3COL do not appear within negation signs: the same goes for (FO+poshP)).

Recommendations

• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• scientific article; zbMATH DE number 88947
• On completeness for NP via projection translations
• Using the Hamiltonian path operator to capture NP
• scientific article; zbMATH DE number 910751

Cited in

(4)

• Using the Hamiltonian path operator to capture NP
• Non-perturbative graph languages, halting problem and complexity
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• scientific article; zbMATH DE number 88947 (Why is no real title available?)

This page was built for publication: Comparing the expressibility of two languages formed using \(NP\)-complete graph operators

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