Would anyone mind explaining what P and NP are?

It's a vast generalization of the cost to verify a problem/solution.

- P means polynomial - NP means nondeterministic polynomial

Roughly polynomial (P) represents the upper bound of the cost to verify, and the polynomial characterization says that given a problem with a certain input (e.g. the input can be the number of training examples in ML training set or the number of constraints/conditions in a general problem— e.g. all the places you want to visit on your next trip, given many "wants" in a group)

When the cost is polynomial relative to the input size it means it can only be finitely larger than the input - that's a characteristic of the polynomial which is just a finite sum of powers of x (the input).

When the cost is nondeterministic polynomial, one way to think about it in what is called a nondeterministic Turing machine. The nondeterministic part refers to the "states" that the machines can transition to from any current state. When the transition can happen to more than one state, we say it's non-deterministic— and can imagine it's determined by some probability.

The general assumption is that polynomial (P) is easier than nondeterministic polnomial (NP). This isn't necessarily the case as there can be arbitrarily large finite numbers (making P solutions intractible)

The P vs NP problem is one of the main open problems and generally considered a crank magnet and general confusion. For a good (likely the best) resource see https://scottaaronson.blog/

▲

dpweb 2 hours ago | parent | prev | next [-]

P and NP are classes of computational problems.

A problem in P can be solved in polynomial time - the computation required grows relatively slowly as the input size increases. Like sorting a list of numbers.

A problem in NP requires exponential time or greater, but a proposed solution can be verified quickly. For example, checking a completed Sudoku puzzle.

It is believed but unproven that all problems in NP are NOT in P.

▲

calfuris an hour ago | parent | next [-]

A problem in NP can have a (positive) solution verified in polynomial time. That's it. Requiring more than polynomial time to solve isn't part of the definition, and in fact it's an open question whether any problems in NP require more than polynomial time to solve.

Every single problem in P is in NP. What is believed but unproven is that some problems in NP are not in P.

▲

SoftTalker an hour ago | parent | prev | next [-]

I have never really understood this, from the time it was first introduced to me in my undergraduate education nearly 40 years ago. It seems to boil down to saying "all unsolvable problems are not in the set of solvable problems" which seems like a tautology. I don't get why "P != NP" is considered so profound.

I feel like I have not yet found the proper explanation. Or I'm just too dense to get it.

	▲	program_whiz an hour ago \| parent [-]
		Not sure you're wanting an explanation, but it comes down more to equivalent algorithms than rigid categories. For example there is a P algo to sort a list of numbers, but not to solve a sudoku (NP). However there is a polynomial algo to check sudoku (spaces ^ 2 if you check every space against every other space for rule violation). However, the reason all NP algos are part of the same category is because you can solve any problem in NP by switching the problem into another problem in the same category and solving that. For example, you can turn sudoku into a graph coloring problem, which is also NP. You can turn sorting (P) into something like balancing a tree, which is also P. The major question is "is there any algorithm that would allow us to change some NP problems into P problems, solve it, then use it for the original problem". E.g. could we take graph coloring and turn it into sorting a list of numbers? So basically, if there is any way to bridge the two, then it might mean every NP problem is actually solvable by a P algorithm, under some transformation. This would be immense because it would completely change the way we solve those algorithms and greatly reduce compute costs. While this seems far-fetched, realize that there are some problems that seem extremely expensive if done the naiive way, but are actually solvable in P. For example, you _could_ write an exponential sorting algo (try every element in every position), but clever people found a way to make it efficient (P). So its possible we just need the right algo to completely change the landscape of computing. However, as you say, its almost self-evidently true that P != NP, but has never been proven so (to do so, we need to prove that no such algorithm can exist). But clearly, solving an exponentially complex problem using a O(log n) algo would be remarkable. To take a concrete example, currently the best algos to exhaustively check a board game like chess or go are exponential (NP). Its easy to verify the winner, but its exponential to enumerate every possible move (e.g. 80^turns states). If we found a polynomial way to solve this (even by converting to something simplified), then it would mean we could exhaustively search chess polynomial to the number of moves (e.g. turns^100). This changes it from "cannot be done in the lifespan of universe" to "its possible with a powerful computer in measurable time". We already use heuristics and estimates to explore the exponential space in efficient time, so if we had a polynomial algo chess, markets, optimization, and other NP problems would be extremely efficient to solve.

▲

bjourne an hour ago | parent | prev [-]

NP contains P. You're thinking of NP-hard problems.

▲

PandaRider 2 hours ago | parent | prev | next [-]

I have taken algorithms courses.

This video explains in detail: https://www.youtube.com/watch?v=YX40hbAHx3s

In short, P means Polynomial time (i.e. markets can solve computation problems efficiently) and NP means Non-Deterministic Polynomial time (i.e. markets can verify solutions of computation problems efficiently but solutions are found by luck).

If P != NP, it means luck CANNOT be engineered and markets are competitive.

▲

super_mario 2 hours ago | parent | prev | next [-]

Wikipedia is a good source on this

P complexity class

https://en.wikipedia.org/wiki/P_(complexity)

NP complexity class

https://en.wikipedia.org/wiki/NP_(complexity)

P vs NP question

https://en.wikipedia.org/wiki/P_versus_NP_problem

▲

VMG 2 hours ago | parent | prev | next [-]

well obviously N=1

▲

convolvatron 2 hours ago | parent | prev [-]

in CS we define a complexity class as a set of problems that have the same growth characteristic. that is for a problem size N, how long does it take in the worst case to find the solution for that problem.

one such class is the Polynomial class, or P, where the time to solution is some fixed exponent of N (like N^2, or 3).

the next big step is NP, which require a polynomial number of nondeterministic steps, whose solution can only be verified in polynomial time. usually solutions to NP problems are exponential in cost with respect to N (like 2^N), but thats not part of their definition.

problems in NP are generally identified by mapping them into a well known problem known to be in NP, where the mapping has to occur in polynomial time.

its an open question as to whether NP as a class can actually be solved in P time, but most people doubt that that is really the case.