[HN Gopher] Asymmetry of verification and verifier's law
       ___________________________________________________________________
        
       Asymmetry of verification and verifier's law
        
       Author : polrjoy
       Score  : 14 points
       Date   : 2025-07-19 23:45 UTC (2 days ago)
        
 (HTM) web link (www.jasonwei.net)
 (TXT) w3m dump (www.jasonwei.net)
        
       | b0gb wrote:
       | Hmm, no reference to the famous P vs NP problem...?
        
         | aleph_minus_one wrote:
         | Or classes related to NP for which we also don't know the
         | answer, such as TFNP
         | 
         | > https://en.wikipedia.org/wiki/TFNP
         | 
         | "TFNP is the class of total function problems which can be
         | solved in nondeterministic polynomial time", i.e. we don't
         | consider decision problems (as for NP), but total functions.
         | 
         | This class contains quite some interesting subclasses, such as
         | PLS (solution can be found via Local Search), PPA (solution
         | exists because of a Parity Argument), PPP (solution exists
         | because of a Pigeonhole Principle), PPAD (solution exists
         | because of a Directed Parity Argument), CLS, ...
         | 
         | In interesting article which explains this topic quite well is
         | https://inference-review.com/article/when-existence-is-ineff...
        
       | weinzierl wrote:
       | _" Interestingly, there are also some tasks that can take way
       | longer to verify than to propose a solution. For example, it
       | might take longer to fact-check all the statements in an essay
       | than to write that essay."_
       | 
       | I think this point is odd. If you could really come up with a
       | proper solution (a correct essay in this case) faster than to
       | verify it then why not produce the correct solution directly
       | instead of verifying.
       | 
       | And if you argue, but I don't want a different correct essay but
       | I want this one verified my answer is that the corrected essay
       | without flaws is also a different one.
        
         | beart wrote:
         | I think I might be confused by what you are stating. Are you
         | saying it depends on your definition of "correct"? I think in
         | this case, "verifiable" is what is meant by "correct", and in
         | which case, if you can't verify it, by definition, it can't be
         | correct, right?
        
       | jkaptur wrote:
       | This essay would benefit from results from computational
       | complexity.
       | 
       | P vs NP, of course, but also the halting problem and Rice's
       | theorem: non-trivial semantic properties of programs are
       | undecidable.
       | 
       | In other words, if you say "this is the solution to that sudoku
       | puzzle", that's easy to verify. "This sudoku puzzle has a
       | solution" is almost certainly much harder to verify. "Here's a
       | program that can solve any sudoku puzzle - _impossible_ (in
       | general).
        
       | visarga wrote:
       | > The ease of training AI to solve a task is proportional to how
       | verifiable the task is. All tasks that are possible to solve and
       | easy to verify will be solved by AI.
       | 
       | I've been saying this for years. Especially related to
       | predictions like "AGI in N years".. no, it will come a different
       | speeds per domain. All proportional to the scale of verification.
       | 
       | Verifiable domains are usually math and code. Games also fit the
       | bill. But for real world tasks there is the 1B people using AI,
       | we verify, the signal is there implicit in the chat logs.
        
       ___________________________________________________________________
       (page generated 2025-07-22 23:01 UTC)