Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
-5
votes
1answer
161 views

Should GCT focus on $PSPACE\not\subseteq P/poly$?

GCT tries to show $P$ is not $NP$ by showing $NP$ is not in $P/poly$. Could it be useful in showing $\Sigma_{i+1}\not\subseteq P^{\Sigma_i}/Poly$ at every $i>0$? Suppose if it turns out that $\...
-5
votes
1answer
585 views

Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?
-5
votes
1answer
246 views

Does a Non deterministic TM halt after the same number of steps on the same input? [closed]

Let $M$ be a Turing Machine (TM) which decides a certain language. Enter an input $x$ to $M$ and let the machine compute on $x$. After some time, $M$ will halt. If $M$ is a deterministic TM, it will ...
-5
votes
1answer
60 views

We know that X3C is NP-complete with |X|=3q and |C|=m. Is this problem still remains NP-complete if |C|<2q? [closed]

Exact-Cover-by-3Sets (X3C) is NP-complete. If the number of classes i.e. |C|<2q then whether this is version of X3C is NP-complete or not?
-5
votes
1answer
302 views

whats the difference between nondeterminism and parallelism? [closed]

pondering another Q/A & the responses on here[1] leads to this question: whats the difference between nondeterminism and parallelism? am aware of basic answers. have some of my own ideas on ...
-5
votes
1answer
100 views

Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
-5
votes
1answer
246 views

Can on every instance P = NP? [closed]

I want to ask a question concerning some aspects of the P vs. NP problem. NOTE: Possibly by "popular" standards i am a crank (i tend towards P=NP), but lets focus on the issue (please with a grain of ...
-5
votes
2answers
655 views

open problems on $NP$-complete? [closed]

How can we find the list of open problems on $NP$-comlpete?
-6
votes
3answers
153 views

Fixed parameter tractability [closed]

Lets say I have an algorithm with complexity $O(n^k)$ where $n$ is the size of the input and $k$ is a parameter. Clearly this is superpolynomial; but in fixed parameter tractability we restrict $k$ to ...
-6
votes
1answer
359 views

Quantum complexity class vs classical complexity class [closed]

What is the relation between BQP complexity class and P and NP?
-6
votes
1answer
151 views

Is the difference of two languages in NP-complete an NP-complete too? [closed]

Given two languages $L_{1} \in NP$ and $L_{2} \in \textit{NP-complete}$ such that $L_{1} \cup L_{2} \in \textit{NP-complete}$, Is $L_{1}$ in $\textit{NP-complete}$ too?
-7
votes
2answers
589 views

Validity implies NP=#P? [closed]

Valid progams for NP imply every solution is a valid answer. NP not equals #P implies not all solutions are answers. Therefore, Validity implies NP=#P. NP is the problem class for ...
-10
votes
3answers
2k views

Parity and circuit complexity

attempt to restate question From the feedback, it is obvious that I have not clearly articulated my point. Also, it is not my intent to be condescending. I very clearly have a notion / idea / ...
-10
votes
2answers
652 views

is every “nontrivial” algorithm Turing-complete?

recently there was a big response here to a question relating to the Church-Turing thesis.[1] this is another question that has nagged at me for close to a decade after studying some areas of TCS (...

1
51 52 53 54
55