[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vp / vr / w / wg / wsg / wsr / x / y ] [Home]
4chanarchives logo
P = NP implications

You are currently reading a thread in /sci/ - Science & Math

Thread replies: 8
Thread images: 2
File: p-np5.jpg (11 KB, 729x197) Image search: [Google]
p-np5.jpg
11 KB, 729x197
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.
Thread replies: 8
Thread images: 2

[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vp / vr / w / wg / wsg / wsr / x / y] [Home]

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.
If a post contains personal/copyrighted/illegal content you can contact me at [email protected] with that post and thread number and it will be removed as soon as possible.
If a post contains illegal content, please click on its [Report] button and follow the instructions.
This is a 4chan archive - all of the content originated from them. If you need information for a Poster - you need to contact them.
This website shows only archived content and is not affiliated with 4chan in any way.
If you like this website please support us by donating with Bitcoin at 1XVgDnu36zCj97gLdeSwHMdiJaBkqhtMK