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
0
votes
0answers
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$ ...
0
votes
0answers
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 ...
0
votes
0answers
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, ...
-1
votes
0answers
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 ...
-2
votes
0answers
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 ...
-2
votes
1answer
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 ...
-2
votes
1answer
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 ...
-3
votes
1answer
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. ...
-3
votes
0answers
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 ...
-4
votes
1answer
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/...
-4
votes
1answer
41 views

Problems people face with computer science professions (outside of work)

I am writing an article for a classroom project shedding light on the major issues that Computer Programmers face outside of work. I am not really looking for anything too in-depth concerning ...

1
9 10 11 12
13