This is just a record of unsubstantiated ideas
So, it's well known that BPP=P if strong random generators exist, essentially because we could use it to simulate random numbers, and if they make a difference (in P time?), it would contradict the assumption that strong random generators exist.
And generally speaking people do believe strong random generators exist.
And I suddenly had a weird thought. Why isn't it possible to apply a similar (a *huge* stretch, admittedly) idea but towards NP problems? I mean, there's nothing that prevents us from accidentally getting an answer to an instance of a NP problem by seeding a PRNG with a magic number.
Of course, the output of the PRNG should not be expected to be legible -- in fact it's almost guaranteed to be gibberish, by definition.
But wait I thought -- isn't this just a compression/decompression problem? Suppose we have temporary access to "god" and somehow was able to gain access to all the questions in NP ever asked by humans and all their answers.... Is it possible to write a compression function to map the questions into the answers?
The thing is, we think P!=NP because we think we need a function that can give answers to ALL possible questions in the problem space... but in fact, we actually can't feasibly ask ALL questions because that would be in EXP. So in fact the size of the problems we want to ask (or formally, the size of all the languages we want to decide whether is accepted?) is in a tractable size, so the answers are also tractable. Of course we believe we don't know the answers, but we already know that it is possible to very luckily stumble into the answer (we have an exponentially small chance, which is what the "N" in NP stands for).
So it seems it is entirely possible that we could accidentally devise a decompression algorithm that somehow decompresses seemingly random bits from a PRNG into answers to NP queries? (As of writing I don't know why I think it's possible...)
No comments:
Post a Comment