# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

611 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
358 views

### Maximize Covering Minimizing the Overlap

I have this problem: Given a collection of sets $S:\{S_{1},...,S_{k}\}$ where each set $S_{j}$ is a subset of $U:\{e_{1},...,e_{n}\}$ universe of elements. I would find-out a subset $C \subseteq S$ ...
210 views

### Is there a series of algorithms for approximating TSP polynomially?

I've began studying some CS recently, and I've faced the TSP. The decision problem version of the TSP is NP-complete, right? I've noticed (and elaborated myself) that there exists several polynomial ...
386 views

### Hardness of Happynet problem

I have been recently researching Happynet in terms of approximation and I have found out that there is a little interest in this topic. What's the reason for this? Are there any related problems, ...
15 views

### If machine learning can cover any CS problem, wouldn't it prove that P=NP?

My (naive) comprehension is that any CS problem, both P and NP, could be expressed as a set of data to expose to ML computation. It doesn't matter how much time the ML algorithm would take to learn ...
20 views

### How to approach SAT-related reduction/proofs? (Double-SAT)

I am preparing for my exam next month and was stuck when it came to SAT reductions/proofs. Could someone help me out in understanding this question? Double-SAT = {< ϕ > | ϕ is a Boolean formula ...
149 views

### Complexity class on quantum computation and classic ones

Does the complexity speedup in superpolynomial by quantum computation mean it is possible to find new algorithm on classic Turing Machine which can speedup in classic Turing Machine in ...
193 views

### What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?

For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...
39 views

### tables of reductions in literature

I'm interested in tables of which problems are reducible to which other problems. Particularly for graph problems, but any such tables/graphs would be neat, just so I know how to look for them. ...
62 views

### Relation between Randomized and Distribution complexity

$DistNP$ is contained in $AvgP$ does not imply that $NP=RP$ by https://dl.acm.org/doi/10.1109/CCC.2011.34. Do we know if $NP=RP$ then $DistNP$ is contained in $AvgP$? or $PP=BPP$ then $DistNP$ is ...
974 views

### Subset-Sum modulo small primes

I was thinking about the strategy of solving Subset-Sum (with a set of size n and integers having n bits each) by using Dynamic Programming (described here: http://en.wikipedia.org/wiki/...