Optimization and Satisfiability in Graph Theory

Output of Algorithms

• Returns 1 for successful completion and 0 for unsuccessful termination.

Optimization Problems

• Involve finding an optimal value (maximum or minimum) for a cost function.
• May be NP Hard.

Satisfiability Problem

• Determines if a given expression holds true for some truth value assignments to its variables.

Key Definitions

• Clique: A complete subgraph within a graph, defined by the number of vertices it contains.
• Reducibility: If a problem L2 can be solved in polynomial time, and L1 can be solved using the same algorithm, L1 reduces to L2 (L1 α L2).
• α: A transitive relation.

Non-Deterministic Algorithms (NDA)

• NDAs can lead to multiple completions based on various choices; e.g., equal numbers in an array can result in many sorted permutations.
• Successful completion: output 1; Unsuccessful: output 0.
• Implicit output statements indicate success or failure through signals.

Decision Problems and their Importance

• Many optimization problems can be reformulated as decision problems.
• A decision problem solvable in polynomial time implies its corresponding optimization problem is also solvable in polynomial time.
• If the decision problem isn't solvable in polynomial time, the optimization problem isn't either.

Maximal Clique Problem

• A maximal complete subgraph in a graph G(V,E) is known as a clique.
• The size of the maximal clique is measured by the number of vertices.
• The Max Clique problem seeks to find the largest clique in graph G.
• The corresponding decision problem checks if G has a clique of size at least k.

Computational Complexity Classes

• Fundamental concepts include P, NP, NP Hard, and NP Complete classes.
• Problems categorized based on the best-known algorithm's computing time.

P Class

• Involves problems where computing time is bounded by polynomials of small degree (tractable).
• Examples:
  • Insertion Sort: O(n²)
  • Merge and Quick Sort: O(n log n)
  • Binary Search: O(log n)

NP Class

• Contains problems with non-polynomial computing time.
• Examples: TSP (O(n² 2n)), Knapsack Problem (O(2^n/2)).
• No known polynomial time algorithms exist for NP class problems, making them intractable.

Deterministic vs Non-Deterministic Algorithms

• Deterministic Algorithm: Every operation's outcome is defined, consistent with computer program execution.
• Non-Deterministic Algorithm: Outcomes are limited to specific possibilities, allowing for arbitrary choices under defined termination conditions.

Non-Deterministic Functions

• Choice(S): Arbitrarily selects an element from set S.
• Success() / Failure(): Signals the outcome of the algorithm.
• Execution time for choice and outcome functions is O(1).

Non-Deterministic Search and Sorting

• Search Example: Non-deterministically identifies an element in a set leading to O(1) complexity.
• Sorting Example (Nsort): Sorts positive numbers by allowing choices for positioning while ensuring order verification.

Understanding Non-Deterministic Algorithms

• They can be interpreted deterministically via unbounded parallelism, where multiple algorithm copies explore choices simultaneously.
• The first successful completion stops other copies.

Non-Deterministic Machine (NDM)

• Fictitious machine capable of choosing the correct element from choices, ensuring a successful outcome in one unit of time.

NPC Theory

• Does not provide methods for polynomial time algorithms for NP Class problems.
• Identifies computational relationships among problems with no known polynomial time solutions.

Categories of Problems

• NP Complete (NPC): If one NPC problem can be solved in polynomial time, all can be.
• NP Hard: If an NP Hard problem is polynomially solvable, all NPC problems can be solved in polynomial time.
• All NPC problems are NP Hard, but some NP Hard problems are not NPC.

Conclusion

• Focus should shift to understanding nondeterministic computations since neither NPC nor NP Hard problems are polynomially solvable.

This quiz covers key concepts in optimization problems and satisfiability related to graph theory. Learn about cliques, cost functions, and the complexity of finding optimal solutions. Challenge your understanding of these important algorithms and their applications.