-2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ You seem to take as a premise that there is no deterministic algorithm that can solve this particular NP-complete problem (whatever it actually is) in polynomial time, which implies there is no deterministic algorithm to solve any NP-complete problem in P time. You've simply assumed that P =/= NP, not proved it. $\endgroup$ Jan 18 at 20:24
  • $\begingroup$ @NuclearHoagie I understand the confusion, I was saying that a deterministic algorithm cannot solve it by definition, as long as I did make it perfectly random. This is because by definition, a deterministic algorithm only works, if a particular input always produces the same output. The idea is that a truly random problem would not always produce the same output for input. $\endgroup$ Jan 18 at 20:42
  • $\begingroup$ @NuclearHoagie their is a very good chance I could be wrong though my knowledge was very limited. $\endgroup$ Jan 18 at 20:42
  • $\begingroup$ This "random oracle" has some mathemticians wrongly led to the conclusion that they could prove $P\ne NP$ this way. Moreover there is no algorithm to generate complete randomness , this only works (perhaps) with physical processes. $\endgroup$
    – Peter
    Jan 18 at 20:46

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Thank you, but I don't quite understand your answer. It is a finite sequence of symbols, the idea is that since it is perfectly random, the only option for the SAT problem is to check every sequence individually due to the problem being constructed perfectly randomly. I don't mean to argue just confused by the answer. $\endgroup$ Jan 18 at 20:14
  • $\begingroup$ The "problems" we consider in comparing P and NP are languages, i.e., sets of finite sequences of symbols. E.g., the problem SAT comprises the set of all finite sequences symbols drawn from some appropriate alphabet that represent satisfiable propositional formulas: there is no notion of randomness in that description of the problem. $\endgroup$
    – Rob Arthan
    Jan 18 at 20:19
  • $\begingroup$ ohh, so it would be impossible to generate a problem using perfect randomness for the boolean satisfiability problem? $\endgroup$ Jan 18 at 20:21
  • $\begingroup$ You could generate a random propositional formula as one input to the algorithm, but the problem is defined to be the set of all inputs that represent satisfiable propositional formulas. I'll add some more to my answer that I hope will explain. $\endgroup$
    – Rob Arthan
    Jan 18 at 20:24
  • $\begingroup$ sorry for my lack of knowledge, but what stops us from constructing the sequences using perfect randomness. $\endgroup$ Jan 18 at 20:25
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .