FIT2014 Lecture Notes - Lecture 20: Finite-State Machine, Vertex Cover, Turing Machine
29 Jun 2018
School
Department
Course
Professor
Lecture 20
Deciding if a string belongs to a language or not VS Verifying that a string belongs to a language
P is intended to contain languages which are efficiently decidable. P is the set of languages for which there is a
polynomial-time decider.
Consider: { people who can kick a football }
- How do you verify that a person can kick a football?
- Give them a ball and get them to try to kick it.
- This procedure is a decider. It enables you to decide whether or not they can kick a football.
Now consider: { university graduates }
- How do you verify that a person is a graduate?
- Can’t do it just by meeting them, testing abilities etc. There is no efficient decider for this set.
- But you can verify it if you have their degree certificate.
- Hard to verify that someone is not a graduate.
A verifier for a language L is a TM that takes, as input, two strings x and y,
- halts for any x, y
- x in the input string
- if x is in L, there exists y such that the TM accepts
- if x is not in L, every y makes the machine reject
- y is called a certificate
- x is accepted if and only if it has a certificate which can be verified.
- Polynomial-time verifier: a verifier with time complexity polynomial in length of x.
(i.e., O(|x|k), for some fixed k, where |x| denotes length of string x)
NP is the set of languages for which there is a polynomial-time verifier.
NP stands for Non-deterministic Polynomial time
NP is intended to contain languages for which membership can be efficiently verified, with the aid of an
appropriate certificate.
Proving membership of NP
To show a language is in NP, you need to:
- specify the certificate
- give a polynomial-time verifier (as an algorithm)
- prove that it is a verifier for the language
- prove that it is polynomial time.
So we have proved that { 3-colourable graphs } is in NP. Remarks: Some of these time estimates are loose
upper bounds. Better estimates are often possible. (E.g., how long does it take to look something up in an
array of size n ?) But if our objective is to show that something is in NP, then all we need to show is that the
time complexity of verification is bounded above by a polynomial (i.e., O(nk), for some fixed k ).
Some languages in NP
- the set of composite numbers
{ x in N : there exist integers y, z such that 1 < y < x, 1 < z < x, and x = y . z }
- SATISFIABILITY: the set of satisfiable Boolean expressions
- 2-SAT
o exactly two literals in each clause
o see the end of the previous lecture
- 3-SAT
o exactly three literals in each clause
- the set of Hamiltonian graphs
o A Hamiltonian circuit in a graph G is a circuit which includes each vertex exactly once. (note:
a circuit doesn’t repeat any vertex or edge)
o A graph is Hamiltonian if it contains a Hamiltonian circuit.
Document Summary
Deciding if a string belongs to a language or not vs verifying that a string belongs to a language. P is intended to contain languages which are efficiently decidable. P is the set of languages for which there is a polynomial-time decider. Consider: { people who can kick a football } Give them a ball and get them to try to kick it. It enables you to decide whether or not they can kick a football. Ca(cid:374)"t do it just (cid:271)(cid:455) (cid:373)eeti(cid:374)g the(cid:373), testi(cid:374)g a(cid:271)ilities et(cid:272). There is (cid:374)o effi(cid:272)ie(cid:374)t de(cid:272)ider for this set. But you can verify it if you have their degree certificate. Hard to verify that someone is not a graduate. Polynomial-time verifier: a verifier with time complexity polynomial in length of x. (i. e. , o(|x|k), for some fixed k, where |x| denotes length of string x) Np is the set of languages for which there is a polynomial-time verifier.
