Information Technology Reference
In-Depth Information
Chapter 2
Investigations Concerning the Structure
of Complete Sets
Eric Allender
Abstract
This chapter will discuss developments bearing on three related research
directions where Somenath Biswas has made pioneering contributions:
•
Isomorphism of Complete Sets
•
Creative Sets
•
Universal Relations
Some open questions in each of these directions will be highlighted.
·
·
·
Keywords
Berman-Hartmanis conjecture
Isomorphism
NP-completeness
·
Creativity
Universality
Mathematics Subject Classification (2010)
Primary 68Q15
2.1 Introduction
How many NP-complete sets are there?
Although there is a trivial and uninteresting answer to this question (namely: there
is a countably infinite number of NP-complete sets), there is a large body of work
investigating the proposition that in actuality there is
precisely one
NP-complete set
(modulo minor encoding details).
Let us clarify what is meant by “minor encoding details”: When we consider the
set SAT of satisfiable Boolean formulae, it is irrelevant if we encode formulae using
round parentheses () or square ones [], or if we write variables in italic font or in
bold face. Any of these choices would lead to a reasonable encoding of SAT; they
all yield encodings of SAT that are equivalent in some sense.
