【math-notes】n=np problem

Posted on Edited on In , Views:

notes. (building)

Abstract

It is about solving problems and finding solutions.
“How hard a problem is to solve” -Computational Complexity.

Turing machine(skip if you are CS student)

Keyword: Boolean->Turing->Shannon->Bell Labs->von Neumann->

Turing claim that there are a kind of machine which can compute any computable sequence, given enough time and memory.

This is the fundation of modern computer - turing machine.
Turing machine is based on boolean logic, which means datas are represented with 1&0s.
With “and”, “or”, “not”, 3 kinds of gates, you can build a system to solve problems step by step.

Transistors can be combined to mimic the logic gates, hence compute anything that is computable.

von Neumann invented the architecture of universal electronic computer, which includes input, output, CPU, memory, blabla.

main

Turing actually proved that not everything is computable, which left a problem for algorithms.
It turn out to be that some problem is harder than other.
Here comes the “P and NP” problem.

  • P Problem means problems can be solved in polynomial time, is relatively easy.
    Including find shortest path, sorting a list of numbers and so on.
    These problems can be solved given enough time and compute power.

  • NP Problem means problems that are easy to verify only when the solution is given.
    P problems are comtained within the NP Problems.
    For example, puzzle or Sudoku, once it is solved, it is much easier to check.

Some previous NP problems are now studied and proved to be P problem, this lead to the question:
Are all the NP Problems really P Problems?
This determines if the computers the ultimate panacea to all problems.

There’s one more concept:

  • NP Complete
    Which means all the difficult problems in NP are equivalent, and if you can prove one of those actually P Problem, all the other as well.

Some scientists have tried to prove that P doesn’t equal NP.
They encountered a mathematical roadblock called the Natural proofs Barrier.
The natural proofs barrier of Razborov and Rudich states that under credible cryptographic assumptions one cannot hope
to separate NP from P by finding combinatorial properties of functions that are constructive, large, and useful.
This basically tells everyone that you can’t prove P not equal NP by usual math.

More

Study of the natural proof barrier leads to other questions like:
How hard is it to determine the hardness of various computational problems. Why it is hard to tell how hard it is?
It opens a new field called meta-complexity.

参考

https://mp.weixin.qq.com/s/tjGs2XfHnQqxwsUD60J1DQ
https://cstheory.stackexchange.com/questions/30680/scope-of-natural-proofs-barrier