Understanding Nondeterministic Computation in Complexity Theory

csce 637 complexity theory n.w
1 / 60
Embed
Share

Explore the motivations behind nondeterminism in computation, examples of problems that utilize it, and how magic steps can be implemented in algorithms for decision-making processes. Discover how Turing machines can simulate human-like magical decision-making abilities and delve into the concept of picking the best option among multiple choices.

  • Complexity Theory
  • Nondeterminism
  • Turing Machines
  • Decision Making
  • Algorithms
rayaanacharya
webr_dut Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. CSCE-637 Complexity Theory Fall 2020 Instructor: Jianer Chen Office: HRBB 338C Phone: 845-4259 Email: chen@cse.tamu.edu Notes 4: Nondeterministic Computation

  2. Nondeterminism Motivations. Turing machine was proposed originally to study human s way of thinking. On each given situation, a Turing machine has a unique reaction (deterministically): (q0, a0) = (q1, a1, V1). However, on a given situation, a human may have options of choosing a reaction from a set of more than one reactions. A smart(est) person may be able to (always) pick the best option (e.g., the best chess player, who seems to be able to always, magically, pick the best option in each step). Our deterministic Turing machine cannot simulate this kind of magical operations. In fact, we do not understand how such a magical decision is made by humans. We want our Turing machines to be able to simulate such magic steps, that on a set of options always pick the best one. 2

  3. Nondeterminism Example 1. Problem SHORSTEST-PATH. Given a graph G, two vertices s and t, and integer k, is there an s-t path of length k? Example 2. Problem Traveling-Salesman. Given a weighted n-vertex graph G and integer k, is there a traveling salesman tour of weight k? Algorithm. 1. for (i=1; i++; i n) magically pick a vertex vi; 2. check that all vertices picked in step 1 are different; 3. for (i=1; i++; i n-1) check [vi, vi+1] is an edge; 4. check ( weight[vi, vi+1] k); 5. if (any test in steps 2-4 fails) return ( no ) else return ( yes ) Algorithm. 1. magically pick an integer h k; 2. v0 = s; 3. for (i=1; i++; i h) magically pick a vertex vi; 4. for (i=1; i++; i h) check [vi-1, vi] is an edge; 5. check vh = t; 6. if (any test in steps 4-5 fails) return ( no ) else return ( yes ) 3

  4. Nondeterminism How do we implement these magic steps? 4

  5. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: 5

  6. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: Pick the correct option among the following: 1. pick v1; 2. pick v2; . n. pick vn 6

  7. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: Pick the correct option among the following: 1. pick v1; 2. pick v2; . n. pick vn Thus, in the execution flow of a deterministic algorithm: pick vi 7

  8. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: Pick the correct option among the following: 1. pick v1; 2. pick v2; . n. pick vn Thus, in the execution flow of a deterministic algorithm: in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi 8

  9. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: Pick the correct option among the following: 1. pick v1; 2. pick v2; . n. pick vn Thus, in the execution flow of a deterministic algorithm: in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi pick vi Always go the correct path 9

  10. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: Pick the correct option among the following: 1. pick v1; 2. pick v2; . n. pick vn Thus, in the execution flow of a deterministic algorithm: in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi pick vi Always go the correct path Thus, a nondeterministic algorithm accepts if there is a path in its computation tree accepts. 10

  11. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: Pick the correct option among the following: 1. pick v1; 2. pick v2; . n. pick vn Thus, in the execution flow of a deterministic algorithm: in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi pick vi Always go the correct path Thus, a nondeterministic algorithm accepts if there is a path in its computation tree accepts. Note: the nondeterministic algorithm does not go through the entire tree. Instead, it always magically picks the correct path in the tree. Thus, its computation time is the length of that path, not the size of the tree. 11

  12. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: Pick the correct option among the following: 1. pick v1; 2. pick v2; . n. pick vn Thus, in the execution flow of a deterministic algorithm: in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi pick vi Always go the correct path How do we implement this in a Turing machine? 12

  13. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: Pick the correct option among the following: 1. pick v1; 2. pick v2; . n. pick vn Thus, in the execution flow of a deterministic algorithm: in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi pick vi Always go the correct path How do we implement this in a Turing machine? (q0, a0) = (q1, a1, V1) unique 13

  14. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: Pick the correct option among the following: 1. pick v1; 2. pick v2; . n. pick vn Thus, in the execution flow of a deterministic algorithm: in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi pick vi Always go the correct path How do we implement this in a Turing machine? (q0, a0) = (q1, a1, V1) (q0, a0) = (q2, a2, V2) (q0, a0) = (q1, a1, V1) unique 14

  15. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi Always go the correct path (q0, a0) = (q1, a1, V1) (q0, a0) = (q2, a2, V2) 15

  16. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi Always go the correct path (q0, a0) = (q1, a1, V1) (q0, a0) = (q2, a2, V2) Can have only bounded number of options 16

  17. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: How do we allow unbounded number of options? in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi Always go the correct path (q0, a0) = (q1, a1, V1) (q0, a0) = (q2, a2, V2) Can have only bounded number of options 17

  18. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: How do we allow unbounded number of options? kinds of options Using binary options to simulate other in the execution flow of a nondeterministic algorithm: pick v1 pick vn .. pick v2 pick vi Always go the correct path (q0, a0) = (q1, a1, V1) (q0, a0) = (q2, a2, V2) Can have only bounded number of options 18

  19. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: How do we allow unbounded number of options? kinds of options Using binary options to simulate other in the execution flow of a nondeterministic algorithm: pick v1 pick vn pick v1 not pick v1 .. pick v2 pick vi pick v2 not pick v2 Always go the correct path pick vn-1 pick vn (q0, a0) = (q1, a1, V1) (q0, a0) = (q2, a2, V2) Can have only bounded number of options 19

  20. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: How do we allow unbounded number of options? kinds of options Using binary options to simulate other in the execution flow of a nondeterministic algorithm: pick 1 pick v1 pick vn pick 0 .. pick v2 pick 1 pick 1 pick 0 pick 0 pick vi . pick v1 10 Always go the correct path pick v1 11 pick v0 00 pick v0 01 (q0, a0) = (q1, a1, V1) (q0, a0) = (q2, a2, V2) Can have only bounded number of options 20

  21. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: How do we allow unbounded number of options? kinds of options Using binary options to simulate other in the execution flow of a nondeterministic algorithm: pick 1 pick v1 pick vn pick 0 .. pick v2 pick 1 pick 1 pick 0 pick 0 pick vi . pick v1 10 Always go the correct path pick v1 11 pick v0 00 pick v0 01 pick vi (q0, a0) = (q1, a1, V1) (q0, a0) = (q2, a2, V2) Can have only bounded number of options 21

  22. Nondeterminism How do we implement these magic steps? When we magically pick a vertex vi in a graph G with vertices v1, , vn: we allow the algorithm to execute a step of the following format: How do we allow unbounded number of options? kinds of options Using binary options to simulate other in the execution flow of a nondeterministic algorithm: pick 1 pick v1 pick vn pick 0 .. pick v2 pick 1 pick 1 pick 0 pick 0 pick vi . pick v1 10 Always go the correct path pick v1 11 pick v0 00 pick v0 01 pick vi (q0, a0) = (q1, a1, V1) (q0, a0) = (q2, a2, V2) Thus, binary options are sufficient for nondeterministic TMs Can have only bounded number of options 22

  23. Nondeterminism Can these magic steps be replaced by non-magic steps?

  24. Nondeterminism Can these magic steps be replaced by non-magic steps? Sometimes YES!

  25. Nondeterminism Can these magic steps be replaced by non-magic steps? Problem SHORSTEST-PATH. Given a graph G, two vertices s and t, and integer k, is there an s-t path of length k? Algorithm. 1. magically pick an integer h k; 2. v0 = s; 3. for (i=1; i++; i h) magically pick a vertex vi; 4. for (i=1; i++; i h) check [vi-1, vi] is an edge; 5. check vh = t; 6. if (any test in steps 4-5 fails) return ( no ) else return ( yes ) Sometimes YES!

  26. Nondeterminism Can these magic steps be replaced by non-magic steps? Sometimes NO!

  27. Nondeterminism Can these magic steps be replaced by non-magic steps? UNKOWN! Sometimes NO! 27

  28. Nondeterminism Can these magic steps be replaced by non-magic steps? Problem Traveling-Salesman. Given a weighted n-vertex graph G and integer k, is there a traveling salesman tour of weight k? Algorithm. 1. for (i=1; i++; i n) magically pick a vertex vi; 2. check that all vertices picked in step 1 are different; 3. for (i=1; i++; i n-1) check [vi, vi+1] is an edge; 4. check ( weight[vi, vi+1] k); 5. if (any test in steps 2-4 fails) return ( no ) else return ( yes ) UNKOWN! Sometimes NO! 28

  29. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, the answer is YES

  30. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, the answer is YES Theorem. If a language L is accepted by a nondet. TM, then L is also accepted by a det. TM.

  31. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, the answer is YES Theorem. If a language L is accepted by a nondet. TM, then L is also accepted by a det. TM. Proof. Just check each path in the computation tree of the nondet. TM.

  32. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, the answer is YES Theorem. If a language L is accepted by a nondet. TM, then L is also accepted by a det. TM. Proof. Just check each path in the computation tree of the nondet. TM. Be careful: avoid being trapped into a non-stopping path.

  33. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, then the answer become very unclear.

  34. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, then the answer become very unclear. In particular, if a problem can be solved by a nondet. TM in polynomial time, can it also be solved in polynomial time by a det. TM?

  35. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, then the answer become very unclear. In particular, if a problem can be solved by a nondet. TM in polynomial time, can it also be solved in polynomial time by a det. TM? Definition. A problem Q can be solved in polynomial-time if there is an algorithm A that solves Q and runs in time O(nc) for some constant c on inputs of length n for all n.

  36. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, then the answer become very unclear. In particular, if a problem can be solved by a nondet. TM in polynomial time, can it also be solved in polynomial time by a det. TM? The famous P = NP? problem

  37. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, then the answer become very unclear. In particular, if a problem can be solved by a nondet. TM in polynomial time, can it also be solved in polynomial time by a det. TM? The famous P = NP? problem There are many (2000+) interesting and important problems that can be solved in polynomial time by nondeterministic TMs: Traveling Salesman, Satisfiability, Scheduling, Independent Set,

  38. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, then the answer become very unclear. In particular, if a problem can be solved by a nondet. TM in polynomial time, can it also be solved in polynomial time by a det. TM? The famous P = NP? problem There are many (2000+) interesting and important problems that can be solved in polynomial time by nondeterministic TMs: Traveling Salesman, Satisfiability, Scheduling, Independent Set, Magically guess a vertex sequence, then verify. then verify. Magically guess a schedule, then verify. Magically guess an assignment, Magically guess a vertex set, then verify.

  39. Nondeterminism Can these magic steps be replaced by non-magic steps? If we do not care the running time, then the answer become very unclear. In particular, if a problem can be solved by a nondet. TM in polynomial time, can it also be solved in polynomial time by a det. TM? The famous P = NP? problem There are many (2000+) interesting and important problems that can be solved in polynomial time by nondeterministic TMs: Traveling Salesman, Satisfiability, Scheduling, Independent Set, But it is unknown whether any of them can be solved in polynomial time without using the magic steps

  40. P and NP NP = the class of (decision) problems that can be solved by polynomial-time nondeterministic algorithms (TMs)

  41. P and NP NP = the class of (decision) problems that can be solved by polynomial-time nondeterministic algorithms (TMs) P = the class of (decision) problems that can be solved by polynomial-time deterministic algorithms (TMs)

  42. P and NP NP = the class of (decision) problems that can be solved by polynomial-time nondeterministic algorithms (TMs) P = the class of (decision) problems that can be solved by polynomial-time deterministic algorithms (TMs) A deterministic algorithm is also a nondeterministic algorithm. Thus, P NP

  43. P and NP NP = the class of (decision) problems that can be solved by polynomial-time nondeterministic algorithms (TMs) P = the class of (decision) problems that can be solved by polynomial-time deterministic algorithms (TMs) A deterministic algorithm is also a nondeterministic algorithm. Thus, P NP Can problems solvable by poly-time nondeterministic algorithms be also solvable by poly-time deterministic algorithms, i.e., NP P or NP = P ?

  44. P and NP NP = the class of (decision) problems that can be solved by polynomial-time nondeterministic algorithms (TMs) P = the class of (decision) problems that can be solved by polynomial-time deterministic algorithms (TMs) A deterministic algorithm is also a nondeterministic algorithm. Thus, P NP Can problems solvable by poly-time nondeterministic algorithms be also solvable by poly-time deterministic algorithms, i.e., NP P or NP = P ? If Yes:

  45. P and NP NP = the class of (decision) problems that can be solved by polynomial-time nondeterministic algorithms (TMs) P = the class of (decision) problems that can be solved by polynomial-time deterministic algorithms (TMs) A deterministic algorithm is also a nondeterministic algorithm. Thus, P NP Can problems solvable by poly-time nondeterministic algorithms be also solvable by poly-time deterministic algorithms, i.e., NP P or NP = P ? good news: many hard engineering problems could be solved efficiently bad news: many crypto-systems would crash If Yes:

  46. P and NP NP = the class of (decision) problems that can be solved by polynomial-time nondeterministic algorithms (TMs) P = the class of (decision) problems that can be solved by polynomial-time deterministic algorithms (TMs) A deterministic algorithm is also a nondeterministic algorithm. Thus, P NP Can problems solvable by poly-time nondeterministic algorithms be also solvable by poly-time deterministic algorithms, i.e., NP P or NP = P ? If No:

  47. P and NP NP = the class of (decision) problems that can be solved by polynomial-time nondeterministic algorithms (TMs) P = the class of (decision) problems that can be solved by polynomial-time deterministic algorithms (TMs) A deterministic algorithm is also a nondeterministic algorithm. Thus, P NP Can problems solvable by poly-time nondeterministic algorithms be also solvable by poly-time deterministic algorithms, i.e., NP P or NP = P ? good news: crypto-systems would stay ensured bad news: we have to find ways to solve hard engineering problems If No:

  48. P and NP NP = the class of (decision) problems that can be solved by polynomial-time nondeterministic algorithms (TMs) P = the class of (decision) problems that can be solved by polynomial-time deterministic algorithms (TMs) A deterministic algorithm is also a nondeterministic algorithm. Thus, P NP Can problems solvable by poly-time nondeterministic algorithms be also solvable by poly-time deterministic algorithms, i.e., NP P or NP = P ? Thus, the question is such important, we got to have an answer!

  49. P = NP? Can problems solvable by polynomial-time nondeterministic algorithms be also solvable by polynomial-time deterministic algorithms, i.e., NP P (equivalently NP = P)?

  50. P = NP? Are problems in NP also in P?

Related


No related presentations.

More Related Content