Data Structure and Algorithm 6 | P-NP and Backtracking


1. P-NP Problem

(1) Longest Increasing Subsequence

Leetcode: 300.

Pseudocode: DP, Time complexity .

Python code,

(2) Polynomal Time

An algorithm runs in polynomial time if its runtime is some polynomial in , which can be written as .

(3) Cobham-Edmonds Thesis

A language can be decided efficiently if and only if it can be decided in time for some .

For example,

can be decided efficiently but,

can not be decided efficiently.

(4) Complexity Class P

The complexity class is a class that contains all the problems that can be solved in polynomial time,

Where stands for Turing Machine.

Common P problems are,

(5) Non-deterministic Turing machine

A nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. For example, BST is an NTM because its time complexity is the height of the tree.

(6) NTM to TM Theorem

For any NTM with time complexity , there is a TM with time complexity .

(7) Complexity Class NP

The complexity class NP (nondeterministic polynomial time) contains all problems that can be solved in polynomial time by an NTM.

Common NP problems are,

From the definition, we can easily know that,

But it is still the most important question in theorical computer science that if

It can be explained simply as if a solution to a problem can be checked efficiently, can that problem be solved efficiently?

2. Backtracking

(1) Definition

Backtracking is a general algorithm for finding the solutions to some computational problems. It abandons a candidate (called backtrack) as soon as it determinates the candidate can not possibily be completed to a valid solution. Backtracking is commonly used to solve some NP-complete questions.

(2) Template

(3) Crosswords I

Find a specific word in a matrix.

Leetcode 79.

(4) Crosswords II

Clean a room by robot.

Leetcode 489.

(5) N-Queens I

Leetcode 51.

Trick 1: how to get the diagonal/anti-diagonal index for a cell in an matrix.

For an matrix, there will be diagonals or anti-diagonals. So the index of a diagonal can be calculated by,

And the index of an anti-diagonal can be calculated by,

Trick 2: Before we put a queen, we have to check three sets.

We don't need to check the rows because we will only put one queen in each row.

(6) N-Queens II

This is just a similar question without requirement for printing the board.

Leetcode 52.

(6) Valid Sudoku

Before we see how to solve a Sudoku, let's first see how we can validate one. This is not a backtracking problem.

Leetcode 36.

(7) Solve Sudoku

Next, let's solve a Sudoku.

Leetcode: 37.

(8) Combination

Combination and permutation problems can also be solved by backtracking.

Leetcode 77.

(9) Combination Sum I

Find all the combinations that sums up to a target value.

Leetcode 39.

(10) Subset

Get the list of all the subsets of a set. Note backtrack doesn't help with this problem because it has to traverse all the cases.

Leetcode 78.

(11) Subset II

Everything is similar but this time the set contains duplicated values. So in this question, the backtracking will work for us.

Leetcode 90.

(12) Permutations

Give all the permutations of a list.

Leetcode 46.

(12) Permutations II

Give all the permutations of a list with duplicate values.

Leetcode 47.

(13) Letter Combinations

Leetcode 17.