P = NP

[Anonymous No.11890457]

I am very likely retarded, but isn't the P = NP problem trivially true?
If you can verify if an answer is correct quickly, couldn't you just try out every answer to solve the problem? Like waht's actually the issue with this solution? Trying out every number is technically polinomial time so idk; where's my million dollars at?

[Anonymous No.11890482]

Yes

[Anonymous No.11890484]

>>11890457
The number of solutions to check can increase exponentially with the size of the problem, even if the amount of time to check each individual one is polynomial. Exponential * polynomial = exponential.

[Anonymous No.11890496]

>>11890484
just do a binomial search. so imagine the number of possible solutions increases for 10k to 100k, you just list all the solutions and look for them with said binomil serch algorithm, the answer is logarithmic*polynomial =/= exponential.

[Anonymous No.11890505]

P=NP?

More like Peepee=No-Poopoo

amirite?

[Anonymous No.11890635]

>>11890505
Hehe PNP tranny

[Anonymous No.11890966]

>>11890457
> couldn't you just try out every answer to solve the problem? Like waht's actually the issue with this solution?
Exhaustive listing is exponential. Let n denote the input size, measured in bits, for the original language L. A certificate C for a verifier machine is polynomially large compared to the input size, let's say p(n). So an exhaustive search would be enumerating at most 2^(p(n)) solutions and simulating them at polynomial cost on the verifier in regards to the input, say in time q(n). So then an exhaustive search, even with a poly time verifier, is in general [math] q(n) \cdot 2^{p(n)} \in \Omega \left(2^n \right) [/math]. A good example for this is the SAT problem, where the certificate is a satisfying solution to the formula.
>>11890496
how would you "binary search" on strings? What order would you induce on them? How would the order actually give you information on which side to cut away? Why does one string for input not working guarantee that another half will?

[Anonymous No.11890988]

>>11890496
you can't binary search them, you can't even order them

[Anonymous No.11890992]

P=NP
[P=NP] * 1/P
N=1

OR
P=NP
P=0

[Anonymous No.11891484]

>>11890992
>mom i posted it again!

[Anonymous No.11891505]

>>11891484
>mom i posted it again!

[Anonymous No.11891865]

>>11890457
No but you can verify the process.

[Anonymous No.11892104]

>>11890457
>trying out every number is technically polynomial time
Really? Why don't you go solve 3-SAT on your laptop then - just check every possible input, right? Fuck it, just go break RSA-2048 and make your billions, after all, you only have to check a finite number of prime factors.

[Anonymous No.11892216]

>>11892104
Hah, what's your gameplan for if you could