# Questions tagged [np]

NP stands for Nondeterministic Polynomial time.

19 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
475 views

194 views

### Who introduced the notion of Non-Deterministic Polynomial time?

In his 1972 paper, Richard Karp provides a definition of NP (section 3, definition 4, p.91). It this the original definition of the class NP or is there a previous one? Edit Edmonds mentions the idea ...
144 views

### Is the following problem in $coNP$?

Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$? At least one $\frac n2\times\frac n2$ minor non-vanish implies rank ...
122 views

### What are some known methods for showing that a class has no complete problems?

The only way that I know of is the way that you can show that $RE \cap coRE$ does not via diagonalization. Mostly curious because if $NP \cap coNP$ has no complete problems then $P \neq NP$. I tried ...
95 views

### About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube

Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set $E$, it can be written as the question of trying to maximize a $n$...
226 views

### Are ill-posed inverse problems in NP?

I'm a physicist who works on inverse problems; I'll explain what these are by means of an example. Consider an object whose refractive index is known; then, the problem of computing scattered ...
282 views

### Finding an equivalent NP-complete instance for this game-theory problem

I apologize if this question is not a good fit for CSTheory. I'm a PhD student who has just started out and I'm working on a game-theory problem in one of my classes. Although my professor hasn't ...
As we know, an unbounded knapsack problem could be described as: $\max \sum_{i=1}^nc_1x_i$ s.t. $\sum_{i=1}^na_ix_i\le b$ $x_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$ And for an 0-1 knapsack problem, we ...