1
$\begingroup$

What are some of the most ridiculous possible claims in computer science that we haven't disproved? E.g. For example the claim that ZPP=exptime is absurd but has not been disproven.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ See List of unsolved problems in computer science. $\endgroup$
    – John Kemeny
    Commented Jun 7, 2020 at 10:24
  • $\begingroup$ None of those are "absurd" $\endgroup$
    – blademan9999
    Commented Jun 7, 2020 at 15:31
  • 1
    $\begingroup$ So say you. Claim: There exists one-way functions (absurd!). Claim: The polynomial hierarchy is finitely high (absurd!). $\endgroup$
    – John Kemeny
    Commented Jun 7, 2020 at 16:15
  • $\begingroup$ What makes ZPP=exptime absurd? $\endgroup$
    – John Kemeny
    Commented Jun 7, 2020 at 16:15
  • 1
    $\begingroup$ It asserts that random data (formally, all but an exponentially small percentage of strings) are in fact a vast store wisdom allowing us to solve exponential time complete problems in polynomial time. Unsuitable strings passed as random may be rejected but will not lead to mistakes. $\endgroup$
    – blademan9999
    Commented Jun 7, 2020 at 18:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.