snippetModerate
How can Computer Science theories and inquiries be resolved?
Viewed 0 times
sciencecantheoriescomputerhowandinquiriesresolved
Problem
It's probably possible to prove that P ≠ NP, that one-way functions exist, and that parity games cannot be solved in polynomial time (yes, I've been reading through this list), but how would we go about proving any of those things? Have there been any proofs to any computer science theories, or answers to any substantial computer science questions (such as the ones in that list)? Are they like mathematical proofs (such as Grigori Perelman's resolution to the Poincaré conjecture)? I know that the P versus NP problem seems out of my league, being a junior in high school, but it's a problem that intrigues me, and I would really like to see how others (if any) have answered other, related questions, because I would like to look into a resolution to the problem.
This isn't a duplicate of this question primarily because physics isn't computer science, and secondarily because, unless I'm mistaken, computer science theories are not proven the same way that theories related to physical sciences are proven. They're more like mathematical proofs in that they're logical (right?).
This isn't a duplicate of this question primarily because physics isn't computer science, and secondarily because, unless I'm mistaken, computer science theories are not proven the same way that theories related to physical sciences are proven. They're more like mathematical proofs in that they're logical (right?).
Solution
Theoretical computer science, to which the questions you state belong, is part of mathematics, and the methods used to resolve questions are the same ones used elsewhere in math, namely the method of proofs. The questions you list are notoriously difficult, and seem to be out of reach for current methods.
In the past, the methods used to attack questions of the sort you describe were purely combinatorial. Recently, Ketan Mulmuley and his students have come up with a different method which employs representation theory (via some algebraic geometry), and is conjectured by them to be one day strong enough to resolve the P versus NP question. Currently, though, the only questions within reach of their methods are algebraic ones like permanent versus determinant rather than Boolean ones like P versus NP.
Since it is widely (though not universally) believed that P is different from NP, many results are proved conditional on this assumption. That is, they hold only if P is indeed different from NP. The area of hardness of approximation, which studies how well different combinatorial problems can be approximated in the worst case (in polynomial time), is a good example: all results in this area are conditional on P versus NP or on some even stronger assumptions.
In the past, the methods used to attack questions of the sort you describe were purely combinatorial. Recently, Ketan Mulmuley and his students have come up with a different method which employs representation theory (via some algebraic geometry), and is conjectured by them to be one day strong enough to resolve the P versus NP question. Currently, though, the only questions within reach of their methods are algebraic ones like permanent versus determinant rather than Boolean ones like P versus NP.
Since it is widely (though not universally) believed that P is different from NP, many results are proved conditional on this assumption. That is, they hold only if P is indeed different from NP. The area of hardness of approximation, which studies how well different combinatorial problems can be approximated in the worst case (in polynomial time), is a good example: all results in this area are conditional on P versus NP or on some even stronger assumptions.
Context
StackExchange Computer Science Q#11906, answer score: 11
Revisions (0)
No revisions yet.