Yao Lirong's Blog

Problem Analysis

CS2112
2019/12/05

From Lecture: Hard problems and undecidability

Computable Problem

Time Complexity

Tractable Problems (P)

Polynomial algorithms: $O(n^k)$ for some k ($k\leq4$)

Exponential Time (EXPTIME)

Exponential Time algorithm: $O((2^k)^n)$

Nondeterministic Polynomial Problems (NP)

e.g.: Hamilton cycles, SAT (Boolean satisfiability), Graph coloring

How would you solve a very hard problem? If you have enough resources (space & time), you can just randomly generate some results and check the result’s correctness.

Therefore, the key is that you have to check the correctness in deterministic time (polynomial time). In fact, all of them can be solved by exponential-time algorithms that essentially try all exponentially many possible solutions, but this approach is infeasible

NP-Complete: All NP problems can be expressed using the three NP examples above. These three problems are said to be NP-Complete. In fact, SAT is the most frequently used one. There are many people working on how to solve well-formed SAT problems in a reasonable amount of time. e.g. You can transform a Hamilton cycle problem into an SAT problem and use those SAT algorithms to solve it

Space Complexity

  • L: logarithmic space
  • PSPACE: polynomial space
  • NPSPACE: nondeterministic polynomial space

Inclusion Relationships

$L\sube P\sube NP \sube PSPACE = NPSPACE \sube EXPTIME$

Unknow Problems

  1. $O(Factoring)\in P$ ?
  2. NP = EXPTIME ?
  3. P = NP ?
  4. L = P ?

because L≠PSPACE, we know that at least one of the inequalities L≠P, P≠NP, and NP≠PSPACE must hold, but we don’t know which.

Incomputable Problems (Halting Problem)

interpret

claim:

  1. we can convert a program to an AST
  2. we can build an interpreter for the AST

We have a simple program p that returns only a boolean value.

If we can’t determine whether such simple programs terminate, then of course we have no hope of determining whether more complex programs do.

1
2
3
4
5
6
7
8
/** @return result of p on input i
	or does not terminate if p couldn't terminate on input i
*/
boolean interpret (Program p, Object i)
    
class p {
    boolean main(Object i){...}
}

method interpretis correct $\iff$ $\forall(p,i)$ p.main(i)==interpret(p,i)

terminate

1
2
/** Return whether p would halt on i */
boolean terminates(Program p, Object i)

Autological & Heterological

A program is either autological or heterological:

  • autological: program is autological if it returns true when provided its own AST (return value for other inputs not defined)

  • heterological: either returns false on itself as input or doesn’t terminate

Self-Reference

You cannot build both interpret and terminates for a program. 

1
2
3
4
5
6
7
8
9
10
class H{
    
    /** returns whether P is heterological (either doesn't terminate or return false) */
    boolean main(Program p){
        if(terminates(p,p))
            return !interpret(p,p); //terminate but returns false, so p is heterological
        else
            return true; // doesn't terminate, so p is heterological
    }
}

can’t directly return !interpret(p,p) because we are not sure whether P will terminate. Therefore, we have to first check whether it terminates or not.

Now we want to pass H itself to H.main

note: H can always terminate no matter what p is (because if p terminates, it calls interpret, which always returns a value if p terminates; if p doesn’t terminate, it just returns a boolean value of true) Therefore, if we pass H itself, it goes into the if (terminates) {} block, which returns ! interpret(h,h) = !h.main(h) Therefore, calling h.main(h) actually returns !h.main(h) But how can h returns the negation of what it’s supposed to return? Therefore, there doesn’t exist a program like h. \

Therefore, we cannot build both interpret and terminate. Since we can and did build an interpreter, terminate is what we can’t really build. That’s the why this problem is called a “halting problem”.

Implications

Theoretical Implications

Every language is either:

  1. too expressive to analyze termination precisely (incomplete)
  2. not expressive to build on interpreter (inconsistent)
  3. makes a program like H illegal (impossible to be both comprehensive and consistent)

practical implications

e.g. Can we write a IntelliJ plugin to check NullPointerException? if NPE is decidable, consider the codes below

1
2
3
h;
x = null;
x.hashcode(); // It should give you an error at this line at compile-time, which means the program can determine whether the program will actually run to this line, which means the program can determine whether h terminates

Reduction: if algorithm for problem A can be used to solve B (with suitable efficiency), A must be at least as hard as B. (In the example of above A: NPE checker B: halting problem)

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/2019-12-05-Problem-Analysis/

Publish date：December 5th 2019, 12:00:00 am

Update date：June 9th 2022, 3:18:32 am

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

CATALOG
  1. 1. Computable Problem
    1. 1.1. Time Complexity
      1. 1.1.1. Tractable Problems (P)
      2. 1.1.2. Exponential Time (EXPTIME)
      3. 1.1.3. Nondeterministic Polynomial Problems (NP)
    2. 1.2. Space Complexity
    3. 1.3. Inclusion Relationships
  2. 2. Unknow Problems
  3. 3. Incomputable Problems (Halting Problem)
    1. 3.1. interpret
    2. 3.2. terminate
    3. 3.3. Autological & Heterological
    4. 3.4. Self-Reference
    5. 3.5. Implications
      1. 3.5.1. Theoretical Implications
      2. 3.5.2. practical implications
Total : 66
2023
2022
2021
2020
2019
NOI CS2112 Logistics Cornell Review CS3110 Manual Journal Tsinghua Book