New answers tagged polynomial-time
0
I'm not 100% sure on this, but I believe that the best known bound on this comes from the construction used for the best known bound on creating oblivious Turing machines. See this Gödel's Lost Letter blog post on the relationship between circuit size and oblivious Turing machines, and in particular the "Open Problems" section.
Given an arbitrary ...
-2
Proving P=NP in the same time shows that such algorithm gives a proof to NP in polynomial time if it's true, assuming a same program appears for infinite times: (assuming $n>1$)
for k=1..inf
x=[result running the k-th program for n^k steps]
if x is a proof then return x
Top 50 recent answers are included
