P = NP implications
- Home
- Board: /sci/ - Science & Math
- Reading: P = NP implications
We respect your right to privacy. You can choose not to allow some types of cookies. Your cookie preferences will apply across our website.
Do you believe that P = NP (why, or why not?)?
And if so, do you also believe that Computer Science will fall as a field since bruteforcing will be viable? Will P = NP remove all value of creativity?
>do you believe
>believe
/religion/
>>7797980
if P = NP then the algorithms for NP problems will need to be written in polynomial time
it is literally the opposite of what you said you fucking dunce
if P = NP then N = 1 xDddddddddDDd
>>7797992
You must be over the age of 18 to post here. Please cease and desist from the use of this site.
>>7798000
irony shitposting is still shitposting
still checked
>>7797980
>Do you believe that P = NP (why, or why not?)?
Yes (When in doubt, do the opposite of what CS majors think)
>since bruteforcing will be viable
Let the max number of computations that any reasonable person wait for be 200yr * 4GHz ~= 2^64
c | max problem size for O(n^c)
1 | 18446744073709551616
2 | 4294967296
3 | 2642245
4 | 65536
5 | 7131
6 | 1625
7 | 565
8 | 256
9 | 138
I wish the "polynomial = tractable" meme would die out. Unless the polynomial power c is less than 4 or 5, you're still fucked [math] \bf { hard } [/math] by it's growth. It's better than the problems size we have now but far practical for many problems.
For example if we find polynomial algorithms for SAT, then converting problems in NP to SAT will cube them in size so any algorithm that isn't linear or quadratic will be next to worthless for most problems.
>>7797980
Are you retarded? People spent loads of time to improve algorithms from n^2 to nlogn, or simialar things.
For example people spent a lot of time on triangulation until an O(n) method was developed, with the naive being O(n^2) and O(nlogn) being the best known for a while.
