co-NP-complete

co-NP-complete

Co-NP-complete refers to the class of problems that are the most difficult problems in the complexity class co-NP, which is the complement of the class NP. These problems are as hard as any problem in co-NP and are defined similarly to NP-complete problems. The term is often used to describe problems that are NP-hard and their complements are also in co-NP. An example of a co-NP-complete problem is testing copositivity of matrices, which is formally similar to SDP and is known to be NP-hard.From: Linear Optimization and Duality [2020], Optimality conditions for linear copositive programming problems with isolated immobile indices [2020]

Computational Complexity

View Chapter

Purchase Book

Published in Craig A. Tovey, Linear Optimization and Duality, 2020

Craig A. Tovey

NP-complete problems are not the same as co-NP-complete problems, though both are NP-hard. If you are lucky, you can solve an NP-complete problem quickly by guessing the answer, and verifying quickly that the answer is correct. For example, to solve the NP-complete IP feasibility problem just defined, you could luckily guess a feasible vector v, and quickly verify that Av≤b, and that v is integer.

Optimality conditions for linear copositive programming problems with isolated immobile indices

View Article

Journal Information

Published in Optimization, 2020

O. I. Kostyukova, T. V. Tchemisova

Copositive models arise in quadratic programming (QP) with linear and binary constraints [8,9], fractional QP [3,10], Graph Theory and Combinatorics [2,11], among others. The diversity of copositive formulations in different domains of optimization (continuous and discrete, deterministic and stochastic, robust optimization with uncertain objective and others) is described in [9,12]. According to Dür [9], CP is ‘a powerful modeling tool which interlinks the quadratic and binary worlds’. Being formally very similar to that of SDP, the copositive programmes are NP-hard since testing copositivity of matrices is co-NP-complete [13]. Different algorithms for copositivity detection are described, for example, in [12,14–16]. A clustered bibliography on copositive optimization can be found in [17].

Explore chapters and articles related to this topic

Computational Complexity

Optimality conditions for linear copositive programming problems with isolated immobile indices