Does the idea of creating a perfectly random problem to solve this have any merit, or is it completely useless quackery?

Question

Statement- If perfect random proves P cannot equal NP

Explanation- The crux of P = NP is not figuring out the answer, but rather proving it, and the mathematical community has been approaching this from the completely wrong direction.

Idea- Rather than try to prove that a NP complete problem has no pattern,predictability, or rules, create an NP complete problem with no pattern, predictability, or rules.

How- The way I am going to attempt to do this, is to create a perfectly random Boolean Satisfiability problem.

Background- By definition, perfect randomness cannot be predicted accurately under any circumstances, and follows no “rules”. An easy way to think about this would be a magical theoretical machine that produces perfectly random numbers, no matter how much information we had, we would never be able to accurately predict the next number the machine produced, and the numbers it generated would follow no rules.

What this means is that if an NP complete problem is created that only uses perfect randomness, then it is impossible for a deterministic algorithm/turing machine to solve it in Polynomial time. The reason it would be impossible to solve in polynomial time, would be that the deterministic turing machine would be forced into a brute force algorithm, which would not solve the NP complete problem in polynomial time. We know the Deterministic Turing machine would be forced into brute force algorithm, because for it to work and create a deterministic algorithm more efficient then brute force, the same combinations of inputs must always produce the same output(s), which is not true with a problem completely created by perfect randomness.

To make this slightly easier to think about, or refute. I outlined the rules of a perfectly random Boolean satisfiability problem. All things about the problem must be generated perfectly randomly, this includes The length of each clause The length of the problem Each literal The order of the clauses, variables, and operations All operations

This problem was generated completely and perfectly randomly, meaning it is unpredictable, has no pattern, and no rules.

Answer 1

You asked for it in your title: yes, that would be quackery.

It doesn't make sense to talk about an NP problem that only uses perfect randomness: an NP problem is just a language (a set of finite sequences of symbols). If you meant a non-deterministic algorithm that only uses perfect randomness, then that again doesn't make sense: non-deterministic algorithms don't involve any notion of probability in their definition, or even randomness, they are best thought of as trying all possibilities simultaneously in parallel.

The terminology here is perhaps a bit confusing. For a simple example, we could consider the problem of finding out whether a number expressed in decimal notation is prime. Let's call that problem PRIME. Then the language in question is the set of all finite sequences of decimal digits that represent prime numbers. We identify the problem PRIME with that set. An algorithm that solves PRIME takes a finite sequence of decimal digits as an input and answers "Yes" if the sequence represents a prime number and "No" otherwise. If we were trying to do this by hand, we might think of a specific input, such as $9573$ as our "problem", but that is just one instance of the general problem that the algorithm is required to solve.

Answer 2

I believe the issue lies in that you have glossed over the step of telling the algorithm which problem it is solving in the first place. Consider for example the perfectly random problem of figuring out the passcode to a four digit lock. There is no efficient approach to guess the number, but once you have the number it is very quick to verify that it is indeed correct (that would seem to be P $\neq$ NP).

The problem is that although you have now defined your problem in general terms, but you have not yet specified it fully. When defining an algorithm to solve a problem, we want to know exactly which problem we are solving. We do not just tell the algorithm "you are trying to guess the code to a 4 digit lock", we say "you are trying to guess the code to the specific 4-digit code whose code is 1234".

The algorithm to solve this would be

def find_code(code):
    return code

Your approach instead depends on not telling the algorithm which code it should guess but only giving it some kind of oracle that will tell which inputs are correct and which aren't, but that these oracles are further more indistinguishable. Then the most efficient way to find and verify solution are

def find_code(oracle):
    for code in range(10000):
        if oracle(code):
            return code

def verify_code(code, oracle):
    return oracle(code)

To put it simply, in order to be considered for whether P = NP, you need to tell me not just that you have an oracle but also how that oracle decides whether an input is correct and then whether I can find an efficient solution depends on whether your particular oracle is P, NP, or neither.

Note: the problem of NP vs NP, can then be reinterpreted$^1$ as the question "is there some way I can tell you what number I am looking for so that if you already know what number I am looking for you can verify that you indeed have the right number while if you do not know the answer the information is nearly useless to you?"; similar to how Penn & Teller in their show try to tell the magician what trick they think he used while not giving the trick away to the audience. $^1$ Althought this interpretation is not as general