[a / b / c / d / e / f / g / gif / h / hr / k / m / o / p / r / s / t / u / v / vg / vm / vmg / vr / vrpg / vst / w / wg] [i / ic] [r9k / s4s / vip / qa] [cm / hm / lgbt / y] [3 / aco / adv / an / bant / biz / cgl / ck / co / diy / fa / fit / gd / hc / his / int / jp / lit / mlp / mu / n / news / out / po / pol / pw / qst / sci / soc / sp / tg / toy / trv / tv / vp / vt / wsg / wsr / x / xs] [Settings] [Search] [Mobile] [Home]
Board
▼ Settings Mobile Home
/sci/ - Science & Math
Return Catalog Bottom Refresh
Name
Options
Comment
Verification
4chan Pass users can bypass this verification. [Learn More] [Login]
File
  • Please read the Rules and FAQ before posting.
  • Additional supported file types are: PDF
  • Use with [math] tags for inline and [eqn] tags for block equations.
  • Right-click equations to view the source.
08/21/20New boards added: /vrpg/, /vmg/, /vst/ and /vm/
05/04/17New trial board added: /bant/ - International/Random
10/04/16New board for 4chan Pass users: /vip/ - Very Important Posts
[Hide] [Show All]

Starting February 1st, 4chan Passes are increasing in price.

One year: $30, Three years: $60

[Advertise on 4chan]
[Return] [Catalog] [Bottom]
Anonymous
01/27/25(Mon)02:09:14 No.16566128
Anonymous 01/27/25(Mon)02:09:14 No.16566128
Suppose we find out that P = NP with a constructive proof that also provides an efficient algorithm. Could we use this to settle other computational complexity problems, such as P vs PSPACE? I recently discovered that time-bounded Kolmogorov complexity is NP-hard, which is related to code optimization. So, could we build a heuristic algorithm to find algorithms for given problems if an efficient solution exists?
>>
Anonymous
01/27/25(Mon)07:52:38 No.16566273
Anonymous 01/27/25(Mon)07:52:38 No.16566273
Yes.
>>
Anonymous
01/27/25(Mon)14:55:02 No.16566587
Anonymous 01/27/25(Mon)14:55:02 No.16566587
>>16566273
And?
>>
Anonymous
01/27/25(Mon)15:58:33 No.16566653
Anonymous 01/27/25(Mon)15:58:33 No.16566653
>>16566128
>Suppose we find out that P = NP
I will suppose no such silly things ...
>>
Anonymous
01/28/25(Tue)22:36:38 No.16568332
Anonymous 01/28/25(Tue)22:36:38 No.16568332
Bump
[Return] [Catalog] [Top]
Post a Reply
Return Catalog Top Refresh
[Advertise on 4chan]
Delete Post: [File Only] Style:
[Disable Mobile View / Use Desktop Site]

[Enable Mobile View / Use Mobile Site]

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.