It is known, there exists oracles A, B s.t.: $P^A = NP^A; P^B \neq NP^B$, showing that any proof of P vs NP must be non-relativizing. Questions: (1) Can we actually use Oracles to separate ...
I'm working on a proof-checker that can verify termination proofs. The fundamental method it provides for constructing such proofs is to translate the program into primitive recursion. Basically, I ...
What open problems in computational complexity theory have the most 'obvious' answers, regardless of whether that answer is true or false? The problems I'm talking about certainly have more 'obvious' ...
When would you read a paper claiming to have settled a long open problem like $P$ vs. $NP$? [closed]
From time to time, people announce papers claiming to have settled long open problems like $P$ vs. $NP$. There have been many attempts, reading them is time-consuming, and finding bugs in their ...
I am trying to build a mathematical model of the availability of a file in a distributed file-system. The system works like this: a node $x$ stores a file $f$ (encoed using erasure codes) at $rb$ ...
After reading a recent post on Church's Thesis, I ran into Turing-Church's Strong Thesis, that may be potentially disproven by advances in Quantum Computing. Does anyone know of a good resource that ...