6533b822fe1ef96bd127cac9
RESEARCH PRODUCT
Logical definability of NP-optimisation problems with monadic auxiliary predicates
Clemens Lautemannsubject
Discrete mathematicsEdge coloringBounded functionPredicate (grammar)Clique numberNp optimization problemsMathematicsdescription
Given a first-order formula ϕ with predicate symbols e1...el, so,...,sr, an NP-optimisation problem on -structures can be defined as follows: for every -structure G, a sequence of relations on G is a feasible solution iff satisfies ϕ, and the value of such a solution is defined to be ¦S0¦. In a strong sense, every polynomially bounded NP-optimisation problem has such a representation, however, it is shown here that this is no longer true if the predicates s1, ...,sr are restricted to be monadic. The result is proved by an Ehrenfeucht-Fraisse game and remains true in several more general situations.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1993-01-01 |