All Questions

I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove between 30% to 80% of the values (distances) that wouldn't ...

It was shown in P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in a lattice that the construction of a shortest nonzero vector of a Euclidean ...

It is crucial to use the right notion of reduction to define completeness inside NP. Different notions of completeness inside NP may have significant impact on the properties of complete languages. ...

I came up with the following problem, but do not know how to analyze it. Let $S$ be an ordered set of integers with size $n$ (i.e., $S=\{1,2,...,n\}$). An interval $INV(a,b)$ covers the elements in $...

I am trying to show a reduction from a problem of ordering problem to an np-hard problem that has approximation poly-time algorithm. My problem is: I have M auctions and in each auction I have N ...

Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever ...