Honestly what the fuck does this even mean...

Honestly what the fuck does this even mean. I come on this board quite often and can understand almost all things on here, but then I see this thread and I'm so fucking confused. So what the fuck does it even mean?

durr, it's mean N=1 or P=0. Isn't that super easy?

Okay fuckdingo In general there are three sets of computational problems: Those that can definitely be solved in polynomial time or less (P), those that can definitely not be solved in polynomial time, only in exponential time (EXP) and those that there is currently no polynomial time algorithm to solve but it hasnt been proven that there is NO polynomial time solution (NP). The question of P=NP is whether there exists a polynomial time solution to any of the NP problems. All NP problems are reducible to eachother so a polynomial time solution to one NP would result in a poly solution to all, which is a big deal.

P and NP are classifications of algorithms that solve problems. P stands for Polynomial time, while NP stands for Non-deterministic Polynomial time.

An example of a problem in P is the sorting problem: You're given a list of unsorted data and asked to sort it. You can write an algorithm that sorts the data in O(nlogn) time. What that means is that if you have a dataset of size n, you can perform n*log(n) operations on that data and have it sorted at the end. As n grows, the number of calculations you need to perform grows polynomially.

An example of a problem in NP is the travelling salesman problem, where you're given a list of coordinates in 2-space and you need to find the shortest route to visit all of those coordinates once and return to your starting point with the least possible distance. An algorithm to solve the TSP might take O(2^n), which means that as n grows, the amount of calculations you need to perform increases exponentially.

P=NP is asking for a proof whether the set of problems in P and NP are equal, or whether there are problems in NP which are not in P. It seems like P != NP but no one has been able to prove it one way or the other.

What's super interesting is that computer scientists have shown that NP problems are connected. IE if you have a solution to one NP problem, you could transform any other NP problem so that it could be solved by that original algorithm. This implies that there may be some common intangible element of hard problems that makes them hard. If anyone could provide a proof that P != NP, it would have far-reaching implications about the way we think about computation and problem-solving. It would be on the level of Godel's incompleteness theorem in terms of philosophical implications

It's a class of problems that double in possible solutions every variable added.

So from 4 variables to 5 variables it increases from 16 to 32 (doubling)

So it goes from 16 tests to 32 tests to see which is right. Another additional variable brings it to 64 tests. AKA doubling.

This is exponential growth in possible solutions to test.

The P=NP question is: Is there a way to check through these solutions in a fast way without brute force.

So for instance, looking for patterns or tricks to the way the variables combine or work together. So far all published work shows only exponential time ways to solve exactly. Although Quantum computers could potentially solve it very fast.

Unfortunately academia is very poor and have horrible methodologies and low intelligence to convey the problem to humans properly. As the language they "write" problems like this in is insufficient and a symptom of their pathetic minds.

To reinforce your understanding of the problem.

It depends on the overlap in shape of each number. For instance a doubling in each number compared to the last additional variable makes it trivial to solve. So in essence the P=NP question is one of untangling.

Would something that can solve NP hard problems in P time necessarily possess any other strange capabilities?

Would a time machine possess any abilities besides traveling in time?

A time machine could solve NP hard problems.

Not really

P is a class of decision (yes/no) problems that can be solved algorithmically in polynomial time, that is the time taken vs the size of the problem scales like n or n^2 or n to any constant, positive power.

NP is a class of decision problems whose solution can be verified in polynomial time. P is naturally part of NP because to verify a solution you can just solve the problem in polynomial time and see if that answer comes out.

However there are a bunch of problems in NP that don't seem to be solvable in polynomial time and actually require exponential time (e.g., 2^n, 3^n) or worse (e.g. n!, n^n), and that's where the whole P vs NP thing comes from. The question is, are these problems inherently harder than the problems in P (P ≠ NP) or are there actually ways of doing them that we just haven't thought of yet (P = NP)? Signs point to the former so far but no proof exists for either of them.

Is it just me, or does the idea of P =/= NP just feel to unreal? I can't really put into words why it feels that way though. It's such an abstract thing.

The easier the problem the more simple it is to write a mathematical solution

The more difficult the problem the more easy it is to check the solution but the more difficult it is to write the mathematical solution.

For some very difficult problems, is there a simpler solution that can easily be checked?

It's essentially asking whether or not finding a needle in a haystack is inherently difficult.

What if P AND N equal one?!

Why?

I don't think it's that far fetched an idea for some problems to be inherently difficult.

In algebra, you don't actually generate an answer - you already have the answer, it is just in an unsimplified form. The algebra is completely determined by the algebra.

Sometimes in math, you get an answer that is not part of an algebra greater than the question and the answer combination. In other words, there might be a class of problems that are not answered by the same algebra and so knowing your way around one algebra doesn't tell you anything about a different algebra.
P=NP is asking if there is a new kind of algebra for problems that cannot be computed in polynomial time, and not just the specific algebra of the case where we can check an answer found by luck or by non-polynomial time algorithms.

A possible proof that P /= NP is the reduction to recursion that most problems enjoy can also be considered special cases of coherent recursion – where the current state of the recursion is dependent on the decoherence of previous states, so at each iteration, the entire history of the recursion could possibly be recomputed, because the prior iterations are in a coherent state until the computation. This would model cases where your decoherent iteration would easily be checked, but future states could not be computed without going through all the possible decoherent states of the recursion up to that iteration.
This is the example of a quantum computation, where the answer can be checked in the same time as the computation by taking advantage of decoherence.
Being able to show that a problem written as a quantum computation bidirectional recursion could not be reduced to a simple recursion would show the algebra of the NP solution to be unique to that problem.
Or not… Modeling Ito Calculus as a bi directional recursion sounds like a nightmare.

It's like the solution is "isolated" from the problem, and it feels wrong.

The solution and the problem (the function that checks) form an algebra - a group - for those numbers only.

>This is the example of a quantum computation, where the answer can be checked in the same time as the computation by taking advantage of decoherence.
I think you mean coherence, decoherence it's what you want to avoid with a Quantum computer.

>it's
is*

>Okay fuckdingo In general there are three sets of computational problems
No

>P and NP are classifications of algorithms that solve problems.
No, and misleading as you haven't explained non-deterministic machines.
>What's super interesting is that computer scientists have shown that NP problems are connected.
This isn't really that interesting or unusual.

No.

Yes.

No.

Not even wrong.

Could you explain non-deterministic machines?

I'm the guy who wrote the one you said yes to but I only really understand the definitions in terms of verifiability rather than the formal machine definitions. I guess the two views of it are supposed to be equivalent but I'm not sure how.

A Turing machine is a set of quadruples that essentially read as, "if you're in state S and you read input X on the tape, do action A and go to state T". You can encode that by ,

If you had two quadruples like and you have non-determinism, because it's not clear whether you should do action A and end up in T, or do action A2 and end up in T2.

In a non-deterministic Turing machine, the answer is: you do whatever. This gives an implicit computation tree, based on which quadruple you did at a particular point. A set is computable by a non-deterministic machine if any of the branches terminates with the right answer: on input n, it outputs yes if n is in the set, or no if the input is not in the set (every problem is generalised in terms of sets in computability).

A problem is in NP if it one branch terminates in the right answer in polynomial time.

The equivalence with "polynomially checking the answer" comes from the following. Suppose on input n you have a branch which terminates in a polynomial amount of time which tells you whether n is in the set. There could be multiple branches, but pick one of them. That path through the computation tree is a witness to the fact that n is in the set. If you take a deterministic machine which simulates that one path, you have a deterministic machine which "verifies" the answer. The reverse direction is pretty similar.

That actually makes a lot of sense, nice explanation.