Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Favorites infavorites:mine
infavorites:1234
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with Search options answers only user 683
10
votes
You are misinterpreting the statement quoted at point 1. We are unable to prove the existence of a single language in NP that is not in P, but we suspect that there are infinitely many, in fact, we su …
answered Jul 8 '14 by Yuval Filmus
1
vote
Given an $O(n^2)$ reduction from $A$ to $B$ and an $O(n^3)$ algorithm for solving $B$, you can solve $A$ as follows: Given an instance of $A$ of size $n$, reduce it to an equivalence instance $B$ of …
answered Dec 4 '18 by Yuval Filmus
5
votes
This is a rather strange question to ask, given that a large majority of complexity theorists believe that P is different from NP. All the evidence we have points at P being different from NP, which i …
answered Sep 18 '15 by Yuval Filmus
5
votes
In order to break a one-way function, it suffices to be able to find a single preimage. Given $x$, $f(2x) = x$, so finding a preimage of an arbitrary input is easy. Hence it's not a one-way function a …
answered Jul 21 by Yuval Filmus
68
votes
It is known that P$\subseteq$NP$\subset$R, where R is the set of recursive languages. Since R is countable and P is infinite (e.g. the languages $\{n\}$ for $n \in \mathbb{N}$ are in P), we get that P …
answered Dec 31 '12 by Yuval Filmus
2
votes
Let me answer your concrete questions: An oracle is a language. One way to describe a language is to give a procedure for constructing it. The construction is not a counterexample to P=NP. It shows …
answered Sep 10 by Yuval Filmus
24
votes
As Raphael explains, this question is ill-posed, since at most one of P=NP and P≠NP should be provable at all. However, a similar question arises in theoretical computer science in several guises, the …
answered Jan 28 '16 by Yuval Filmus
2
votes
First of all, it is not clear what you mean by an algorithm which is able to solve any problem in NP; usually one algorithm solves one problem. However, given a polynomial time algorithm for solving s …
answered Apr 15 '15 by Yuval Filmus
2
votes
Here is a more direct proof. Suppose that $P=NP$. In particular, SAT can be solved in polynomial time. Therefore $P^{SAT} \subseteq P^P = P \subseteq coNP$.
answered Sep 24 '17 by Yuval Filmus
30
votes
We won't necessarily see any effects. Suppose that somebody finds an algorithm that solves 3SAT on $n$ variables in $2^{100} n$ basic operations. You won't be able to run this algorithm on any instanc …
answered Dec 30 '14 by Yuval Filmus
5
votes
First, let me start by explaining what Boolean circuits are. You are probably familiar with Boolean formulas — these are formulas of the sort $(a \land b) \lor (\lnot a \land \lnot b)$. We can represe …
answered May 10 '18 by Yuval Filmus
2
votes
You ask Doesn't polynomially bounding the length of possible solutions to a given instance mean that there are only polynomially many possible solution candidates? In fact, the number of binary …
answered Mar 18 '17 by Yuval Filmus
6
votes
The time-hierarchy theorem shows that for each $k$ there are problems solvable in time $O(n^{k+1})$ but not in time $O(n^k)$; this problem is (roughly) the halting problem for Turing machines running …
answered Aug 24 '15 by Yuval Filmus
5
votes
The polynomial hierarchy is not $\mathsf{DTIME}(n^k)$ for various $k$, but rather a polynomial time version of the arithmetical hierarchy.
answered Nov 27 '16 by Yuval Filmus
1
vote
A deterministic polynomial time machine for a language $L$ can easily be converted to a non-deterministic polynomial time machine which has the same operational semantics (that is, it operates determi …
answered Dec 20 '15 by Yuval Filmus

15 30 50 per page