[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 / qst / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vp / vr / w / wg / wsg / wsr / x / y ] [Search | Home]
4Archive logo
P = NP implications
If images are not shown try to refresh the page. If you like this website, please disable any AdBlock software!

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: [iqdb] [SauceNao] [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
Thread DB ID: 445197



[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 / qst / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vp / vr / w / wg / wsg / wsr / x / y] [Search | Home]

[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 / qst / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vp / vr / w / wg / wsg / wsr / x / y] [Search | 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.
This is a 4chan archive - all of the shown content originated from that site. This means that 4Archive shows their content, archived. If you need information for a Poster - contact them.
If a post contains personal/copyrighted/illegal content, then use the post's [Report] link! If a post is not removed within 24h contact me at wtabusse@gmail.com with the post's information.