Loic Stoic's user avatar
Loic Stoic's user avatar
Loic Stoic's user avatar
Loic Stoic
  • Member for 1 year, 6 months
  • Last seen this week
4 votes
0 answers
49 views

Are there any probabilistic models of computation that can strongly simulate themselves?

2 votes
1 answer
71 views

Why doesn't the Deutsch Jozsa algorithm on a classical computer show P != BPP?

2 votes
0 answers
40 views

Quantum search with input as a classical circuit

1 vote
2 answers
77 views

Are there problems in NP that would solve P vs NP, but are not NP complete

1 vote
1 answer
50 views

Does $\texttt{Oracle-SAT} \leq_T^P \texttt{SAT} \iff \texttt{P} \neq \texttt{NP}$, and is this possible?

0 votes
1 answer
42 views

Do reductions (in NP and other classes) follow a linear path?

0 votes
1 answer
70 views

Why aren't promise problems just decision problems; can't we encode the promised inputs in the alphabet?

0 votes
1 answer
68 views

Does $\texttt{DTIME}(O(1))$ contain only finite languages?

0 votes
0 answers
35 views

Is Quantum Search (SAT with only oracle access) NP-hard (and not NP-complete)?

0 votes
0 answers
12 views

Would proving that finding a satisfiable input is intractable prove that SAT is intractable? [duplicate]

0 votes
1 answer
88 views

Time complexity to convert a truth table to a boolean circuit

0 votes
0 answers
34 views

Reduction between problems where problem A solves problem B with probability $\frac{2}{3}$

0 votes
1 answer
63 views

SAT with every variable occuring exactly once

0 votes
1 answer
34 views

"Succinct circuit representation" on Turing machines?

0 votes
1 answer
31 views

Representing classical circuits with quantum gates