Is P = NP?

>>8485373
Maybe

50%

Either it is or it's not

>>8485385
Idiot. It's either 0% or 100%.

>>8485373
Divide both P by P
0=N

>>8485373
Partially.

>>8485373

Yes. If N = 1.

Aren't there a lot of P = NP that are already solved?

I'm not a computer science major but I thought P = NP was about building algorithms to solve complex problems and many complex problems have already been solved with algorithms.

File: turing_machine.gif (19KB, 400x350px) Image search: [Google]

19KB, 400x350px

I know this is a troll question but since the only thing I know about is complexity theory

Since P=NP seems to be hard to solved, many theorists look for related questions.

----

For example, it's relatively easy to get random-looking bits from nature to use in our computer, so a natural question is to ask, how much power do algorithms that can use randomness have?

An easy example is quicksort, where you randomly choose the pivot, and this is crucial in arguing that it's average case nlogn complexity. In fact there are many many applications where the only polynomial-time algorithm we have is one that uses randomness (of course, accounting for a arbitrarily small amount of error), see the "polynomial identity testing" problem.

However there have been advancements that show that BPP, the class of polytime algorithms with access to randomness (I'm skipping over some subleties) is equal to P, by showing that this is true if "hard" functions exist (functions that can't be computed quickly).

----

Another related question is the class of P/poly, these are polynomially sized circuits. Turns out that P/poly can be roughly simulated by real electrical circuits, so it might be interesting to see if these have more power. In fact, P/poly contains BPP. The idea is that maybe there isn't a single machine that can solve NP-complete problems like 3SAT for any input length, but for each input length, we can give a different, smallish (in the size of the input) machine that solves the problem efficiently. Although that doesn't show P=NP, that basically makes NP-complete problems tractable.

Unfortunately, the Karp-Lipton theorem shows that if NP is contained in P/poly, then the polynomial hierarchy collapses. Don't have time to explain it but it's basically very very unlikely, similar to how unlikely P=NP is.

Hope someone learned something from this, let me know if I need to explain a definition or something.

>>8485460
>BPP, the class of polytime algorithms with access to randomness (I'm skipping over some subleties) is equal to P
Sorry, I meant imply, not show. The results show that BPP is likely to be equal to P, but not certain.

>>8485391
And if you calculate the probability field between 0 and 100 you get 50, you fucking mong.

>>8485396
>0
almost fell for that bait

File: huh.jpg (26KB, 631x352px) Image search: [Google]

26KB, 631x352px

>>8485453
What if P = 0?

>>8485373
Yes. The algorithm is just incredibly difficult to invent.

>>8485455
Your question makes no sense.

>>8485396
P/P=1 though, unless P=0

>>8485373
N=1

Million dollars please.

Is P=NP?...

Or DOES P=NP?