# Question
Title: Difference between computation in proposition proof and definitional computation?
As stated in equality at nLab, "computational equality" is about computational steps which take for example, $s(s(0))+ s(0)$ to $s(s(s(0)))$ and it acts exactly and can be considered same as definitional equality (at least in type theory).

But then if we consider $p$ in $p:Id\_\mathbb{N}(a+b, b+a)$ as computation steps taking $a+b$ to $b+a$ then what is the difference between computation steps in $p$ and computation steps in above mentioned computational equality which prevents $p$ to be considered sort of a definitional equality? Are they of different computation level/form?

Or in other words, if I have got it correctly, what is the difference between $p$ in $p:Id\_\mathbb{N}(a+b, b+a)$ and $p'$ in $p':Id\_\mathbb{N}(s(s(0))+s(0), s(s(s(0)))) $ so that one can be considered almost the same thing as definitional equality but not the other one?

As an example following are the Agda codes in proving above mentioned reactions from Programming language foundations in Agda: Natural Numbers and \[Programming language foundations in Agda: Proof by induction\]\[3\]correspondingly:

```
_ : 2 + 3 ≡ 5
  =
-
  begin
    2+3
  ≡⟨⟩    -- is shorthand for
    (suc (suc zero)) + (suc (suc (suc zero)))
  ≡⟨⟩    -- inductive case
    suc ((suc zero) + (suc (suc (suc zero))))
  ≡⟨⟩    -- inductive case
    suc (suc (zero + (suc (suc (suc zero)))))
  ≡⟨⟩    -- base case
    suc (suc (suc (suc (suc zero))))
  ≡⟨⟩    -- is longhand for
    5
  ∎

```

```
+-comm : ∀ (m n : ℕ) → m + n ≡ n + m
+-comm m zero =
  begin
    m + zero
  ≡⟨ +-identityʳ m ⟩
    m
  ≡⟨⟩
    zero + m
  ∎
+-comm m (suc n) =
  begin
    m + suc n
  ≡⟨ +-suc m n ⟩
    suc (m + n)
  ≡⟨ cong suc (+-comm m n) ⟩
    suc (n + m)
  ≡⟨⟩
    suc n + m
  ∎

```

In my understanding both thing are computational steps that take you from left hand side to the right hand side!

Would you please answer it both intuitively and technically?

**P.S.** I found the following piece in Homotopy Type Theory(§1.1 p.22) which I thought might be the answer to part of my own question:

> Whether or not two expressions are equal by definition is just a matter of expanding out the definitions; in particular, it is algorithmically decidable (though the algorithm is necessarily meta-theoretic, not internal to the theory).

I guess the above paragraph is talking about $\alpha$ and $\beta$ expansions. But if that is true then it raises the question that: What does a proof of a proposition has in addition to function application that makes it a different equality? Is it that beside application we do have function definitions as well in a proof definition?!

# Answer
What Agda is showing you in the source code in *both cases* are the propositional proofs, i.e., elements of the identity type. In Agda the judgemental (definitional) equality is *invisible* to the user. Agda uses it in the background to verify that terms have required types. When it has to compare $a$ and $b$, it normalizes both of them (based on judgemental equalities, such as $\beta$-reduction) and compares the normalized values for syntactic equalities. There is a theorem which says that $a$ and $b$ are judgementally equal if, and only if, they have syntactically equal normal forms.

When judgemental equality has the property that things are equal preciely when they have syntactically equal normal forms, then people sometimes call it *computational equality* because it "computes" by computing normal forms. There is a lot of confusion in terminology.

To test judgmental equality in Agda, we can use `refl` to show that two things are judgmentally equal (because the rule for `refl` states that `refl a` has type `b ≡ c` if, and only if, `b` and `c` are both judgmentally equal to `a`). Here are some examples:

```
 open import Relation.Binary.PropositionalEquality
 open import Data.Nat

 -- this works, the normal form of 2 + 3 is 5
 p : 2 + 3 ≡ 5
 p = refl

 -- this works, the normal form of 0 + m is m
 q : ∀ m → 0 + m ≡ m
 q _ = refl

 -- this does not work, because the normal form of m + 0 is m + 0
 -- r : ∀ m → m + 0 ≡ m
 -- r _ = refl

```

You can *also* show that $2 + 3 = 5$ by providing an element `p'` of `2 + 3 ≡ 5` which is not `refl`, such as the one you posted in the question. In the text you read, they were just trying to demonstrate the normalization steps by making them explicit as elements of an identity type (without saying so explicitly, probably). The thing to remember is that in Agda you will *never* see "a proof of judgemental equality", as that always happens in the background.
> 3 votes

---
Tags: type-theory, dependent-types, equality
---


# Question
Title: Isn't ZKP is a reduction to a hard problem, rather than true zero knowledge?
Take for example "Hamiltonian cycle for a large graph". The proof works by starting with a graph G that contains a hamiltonian cycle, then constructing an isomorphic graph H, and then either showing the mapping between the graphs G and H or releaving the cycle in H.

It is said that we prove that that we know a hamiltonian cycle in G without revealing it.

But this assumes the verifier does not have unlimited computational power. If he had it, he could ask to reveal the cycle in H, and use his unlimited computational power to work out the isomorphism. I understand that if the verifier had unlimited power, he could find the cycle in G directly. But that's not my point. What I find strange is that we are relying on "hard problems" in the proof itself.

Are there ZKP protocols that do not rely on hard problems? Hard problems are only hard according to the state of the art. It is not proven that NP is not P, therefore, in my mind, this sounds like security through obscurity in some sense.

# Answer
One of the most basic assumptions in cryptography is the existence of hard problems, even on a very conceptual level. For example, to establish a secure communication channel, you want your cipher to impose problems on eavesdroppers which they cannot solve.

The problem is that the existence of hard problems generally has (severe) impact to questions in complexity theory. The most attractive problems for cryptography are those in $\mathsf{NP}$, in particular because, assuming $\mathsf{NP}$ has intractable problems, these have nice asymmetrical properties: Although you can *verify* a solution efficiently, it is infeasible to *find* one. However, establishing intractable problems in $\mathsf{NP}$ necessarily entails proving $\mathsf{P} \neq \mathsf{NP}$.

Furthermore, some cryptographic primitives imply the existence of hard problems *even without basing on the hardness of a particular problem*. For example, the existence of one-way functions, which are essentially the most basic cryptographic primitive, implies $\mathsf{P} \neq \mathsf{NP}$. We also know one-way functions exist if and only if PRNGs exist, so it is clear one-way functions are not an isolated case (whose existence is hard to establish). Also, asymmetric cryptography implies the existence of either of these primitives. (Read more on Impagliazzo's five worlds if you are interested in these issues.)

Modern cryptography is highly dependent on complexity theory for its assumptions. Since that is the case anyway, it only seems natural to embrace the conjectures of complexity theory too.
> 1 votes

# Answer
The zero-knowledge protocol you describe in your computation is an example of *computational zero-knowledge*. A more stringent requirement is *statistical zero-knowledge*, and the corresponding class of languages is $\mathsf{SZK}$. The classical example is graph non-isomorphism, see for example slides of Eli Biham. In fact, this protocol is *perfect zero-knowledge* ($\mathsf{PZK}$).

For more on statistical zero-knowledge, see for example Sahai and Vadhan, A complete problem for statistical zero knowledge.
> 0 votes

---
Tags: proof-techniques
---


title: CLIQUE $\leq_p$ SAT

text:
# Question
Title: CLIQUE $\leq_p$ SAT
i'm trying to reduce CLIQUE to SAT:

* Given: Graph G=(Vertices V, Edges E) and $k \in \mathbb{N}$
* Output: Formular F such that if G contains a complete subgraph of size k, the formular is satisfiable (and vice versa).

I tried doing it the way Cook/Levin showed that SAT is NP-complete by introducing a set of booleans $v\_i$ for each vertex and $e\_{i, j}$ for an edge going from $v\_i$ to $v\_j$. Now if $v\_i$ is part of the clique, then $e\_{i, j}$ must be true iff $v\_j$ is also in the clique.

So we can conclude, that $v\_i \land v\_j \implies e\_{i, j}$ and this is for true for at least $i, j \in \\{0, ..., k - 1\\}$ and $i \neq j$. Also we need to make sure that no edge that doesn't exist can be set to true: $\bigwedge\_{(i, j)\notin E} \lnot\\, e\_{i, j}$.

I don't know if im on the correct way or if I might miss something.

1. How would I restrict the formular $v\_i \land v\_j \implies e\_{i, j}$ to be true for at least k variables?
2. Is this way in poly-time?
3. Is there any better way?

# Answer
There are many ways to reduce CLIQUE to SAT. Probably the simplest is as follows. Suppose that we have a graph $G = (V,E)$, and interested in a $k$-clique. We will have $k|V|$ variables $x\_{iv}$, whose intended meaning is "the $i$th vertex of the clique is $v$". The constraints are:

* There is an $i$th vertex: for all $1 \leq i \leq k$, $\bigvee\_{v \in V} x\_{iv}$.
* The $i$th and $j$th vertices are different: for all $1 \leq i \< j \leq k$ and $v \in V$, $\lnot x\_{iv} \lor \lnot x\_{jv}$.
* Any two vertices in the clique are connected: for all $1 \leq i \< j \leq k$ and $v,u \in V$ such that $(v,u) \notin E$, $\lnot x\_{iv} \lor \lnot x\_{ju}$.
> 5 votes

---
Tags: satisfiability, clique, polynomial-time-reductions
---


# Question
Title: Is there a way to modify Kadane's Algorithm such that we know the resulting subarray?
Kadane's Algorithm is an algorithm that solves the maximum subarray problem by clever dynamic programming. Is there a way to further modify the algorithm so that we would get to know the resulting subarray that produces the corresponding maximum sum?

PS: I don't know whether I should post this here, or Stack Overflow, or both.

# Answer
> 3 votes
Yes, you can.

Kadanes's algorithm keeps the value of the best subarray in a variable, let's call it `best_sum`. Notice the invariant in the algorithm. `best_sum` will always (after each iteration) contain the value of the maxium subarray of the prefix of the array that you already visited. Additionally you know the best suffix sum of the current prefix, let's call it `current_sum`, which you use to update `best_sum`.

You just need to do the same thing with the position. Introduce three more variables `current_startindex`, `best_startindex` and `best_endindex`. `current_startindex` tells you, at which position the current best suffix starts. `best_startindex` and `best_endindex` indicate the start and end of the best subarray from the visited prefix. Keep those variables valid in each iteration. E.g. Whenever you update `current_best`, also update `current_startindex`. And whenever you update `best_max`, also update the `best_startindex` and `best_endindex`, so that at the end of each iteration the value is correct.

After iterating over the complete array, `best_sum` will contain the sum of values of the maximum subarray, and `best_startindex` and `best_endindex` will tell you the positions.

---
Tags: algorithms, maximum-subarray
---


# Question
Title: Seeking nontrivial small SAT/UNSAT instances
I need SAT instances, involving 9 to 20 variables. They need to be hard to solve for humans. Both SAT and UNSAT instances are needed.

I tried random-SAT generators on the web, but the results were not satisfactory because they are trivial. A good example of what I'm looking for is the following 4-variable instance from *The Art of Computer Programming*: $$12\bar3, 23\bar4, 134, \bar124, \bar1\bar23, \bar2\bar34, \bar1\bar3\bar4, 1\bar2\bar4.$$

# Answer
To build a satisfiable instance, start by picking an assignment to the variables that will be a solution. Then, randomly generate clauses that are satisfied by this assignment. Add as many clauses as desired. If you add enough clauses, then with high probability your chosen solution will be the only one, and the problem will be non-trivial.

For instance, suppose your assignment is $x\_1=\text{True}$, $x\_2=\text{False}$. Then you could add any subset of the clauses $x\_1 \lor x\_2$, $x\_1 \lor \neg x\_2$, or $\neg x\_1 \lor \neg x\_2$. For example, one random formula you could generate might be $(x\_1 \lor x\_2) \land (\neg x\_1 \lor \neg x\_2)$.

To build an unsatisfiable instance, proceed as above; then add one more clause that is violated by the solution you chose in advance. If you added enough clauses, it is likely that there will be no other solution, so the problem will be unsatisfiable. Check with a SAT solver just to be sure.
> 1 votes

# Answer
I will do a quick calculation to show that small instances are rare. Consider an UNSAT instance. Suppose it’s $k$-SAT and every clause has exactly $k$ literals. Then there are at least $k$ variables, or some clauses will be trivial. So there are $2^k$ assignments and all of them have to be unsatisfiable. An assignment is unsatisfiable if there is a clause, in which all literals are false. When this happen, let’s call the assignment is covered by the clause. So your aim is to cover the entire $2^k$ assignments by clauses. But in this case, a clause can cover at most 1 assignment, so there are at least $2^k$ clauses in order to be unsatisfiable. When $k=6$, this is 64 and this is optimal. When $k=9$, this is 512. When $n\>k$, the best case doesn’t change, but the probability shrinks as there is more noise.
> 0 votes

---
Tags: satisfiability
---


# Question
Title: Intersection of O(n) expanding circles with line from the origin
I am interested resolving a programming challenge problem, but I'm struggling obtaining an efficient solution.

> Consider yourself as a point located on the origin $(0,0)$ of an infinite two-dimensional flat world. There are $n$ sea waves surrounding you, each one modeled as a circle with center $(x\_i, y\_i)$, initial radius $r\_i$, and propagation speed $s\_i$, so that the radius of wave $i$ as a function of the time $t ≥ 0$ is $r\_i + s\_i \cdot t$. You choose any fixed direction and run “forever” at speed $p$. Will you be able to scape?

Some helpful restrictions given as assumptions are provided:

> * $1 ≤ p ≤ 1000$
> * $3 ≤ n ≤ 10^4$ \[the number of circles $c\_i$\]
> * $−1000 ≤ x\_i,\\;y\_i ≤ 1000$
> * $1 ≤ r\_i ≤ 1000$
> * $0 ≤ s\_i \< p$
> * Except for $n$, all numbers are real, with at most three digits after the decimal point.
> * Initially, you are strictly outside all the waves.
> * There are not precision errors.

My solution so far is quite simple (I have programmed it in C++):

* Each "fixed direction" to run forever is solely determined by the angle of that line with the X axis, namely $0 \leq \theta \< 2 \pi$.
* For each $\theta \in \[0, 0.001, 0.002, \dots, 2\pi)$:
    + Recall that the map is within the square $\[-1000, -1000\]$ to $\[1000, 1000\]$, and the furthest distance between $(0,0)$ and any point in the map has distance $1000\sqrt{2}$. We advance at $p$ speed, so at most we will compute $1000\sqrt{2}/p \approx 1414/p$ iterations.
    + For each $t \in \[0, 0.001, 0.002, \dots, 1414/p\]$:
        - My position at time $t$ in line $\theta$ is $pos\_t = (\cos \theta \cdot t \cdot p, \sin \theta \cdot t \cdot p)$.
        - Check whether $pos\_t$ is inside any sea wave at moment $t$. Basically, check if the distance between $pos\_t$ and the center of each circle is less than that circle's radius at moment $t$, namely $r\_i + s\_i \cdot t$. If so, bad luck; we're done with this $\theta$ and we continue the search.
        - If not, try with next $t$.
    + If no intersection is found after iterating all $t$s, then you will be able to scape (through line with angle $\theta$).
* If all $\theta$s got some intersections, then we are not able to scape.

This solution has cost $\Theta(6000 \times 1400 \times n)$, which is impractical for $n \leq 10^4$. Informally, and without being precise, the multiplicative term may be $O(n^3)$ if $n \leq 10^4$ is considered. Plus, it may not be correct, as I am assuming that $\Delta t = 0.001$ is fine; same for the angle.

---

I have thought about another idea, which is reducing systematically $\theta$. For instance, let's imagine that we've got a circle at $C = (5, 5)$ (in the line of $\theta = \pi/2$) with some small radius. From the beginning, we know that angles $\theta = \pi/2 \pm \alpha$ will never be an option, being $\alpha$ determined by tangent lines from $(0, 0)$ to $C$ and $t$; the more time passes, the higher $\alpha$ will be and thus the wider will be this range of restricted angles.

So, at moment $t$ we have a set of ranges of possible $\theta$s, and that range is reduced as long as $t$ increases (unless all waves have speed 0, for sure).

But how to continue from there? I see the same problems as with my implementation: determining $\Delta t$ and $\Delta \theta$.

---

I ask for your help to find a better algorithm. I suspect that there may be an algorithm that is just $O(k n)$ or $O(k \cdot n \log n)$ with $k$ being reasonably small.

# Answer
> 5 votes
The solution outline:

**Step 1.** Verify, that all the initial (at the moment $t=0$) wave circles don't contain your starting point $(0,0)$. If yes, then continue - otherwise exit, no escape.

**Step 2.** For each wave circle $W\_i$ you need to find an *escape sector* \- the range of directions, where the escape is guaranteed.

Imagine a circle of your possible positions at moment $t$ with center in $(0,0)$ and radius $pt$ \- we'll call it the circle $C$. Let's consider what will happen with circles $C$ and $W\_i$ with time. Originally (when $t=0$) the circle $C$ is just a point at $(0,0)$. Then, with time increasing, the expanding circle $C$ will at first touch the expanding circle $W\_i$ at a single point, then intersect it at two points. Moving further, at some point of time the expanding circle $C$ will touch the circle $W\_i$ again at a single point, then it will contain the circle $W\_i$ completely (because $p \gt s\_i$).

Two intersection points between circles $C$ and $W\_i$ define a *no-escape sector*. This sector angle $\alpha$ grows from zero to some **maximal** value and then decreases to zero again. Cosine of this half-angle at the moment of time $t$ can be found from the triangle with all known sides:

$$\cos(\frac {\alpha} {2}) = \frac {(pt)^2+d\_i^2-(r\_i+s\_it)^2} {2d\_ipt}$$

where $d\_i = \sqrt{x\_i^2+y\_i^2}$.

You need to find positions of intersection points, which will give you **this maximal angle value**. In order to do that you can take first derivative of the non-escape sector half-angle by time and set it to zero - that will give you the moment of time when the non-escape sector is maximally wide. This moment of time $T\_i$ will be:

$$T\_i = \sqrt{\frac{d\_i^2-r\_i^2}{p^2-s\_i^2}}$$

Knowing the non-escape sector you'll easily find the escape sector.

**Step 3.** If intersection of all the escape sectors is non-empty, then the escape is possible.

The algorithm time is obviously $O(n)$.

---
Tags: algorithms, computational-geometry
---


# Question
Title: Student Course Allocation Problem with Many Constraints
**Problem statement**

In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students.

$i$-th section has:

1. A student capacity: $cap\_i$.
2. Two lecture timings. (Formally, each section has two elements from $S$ associated with itself, where $S$ contains all lecture timings.)
3. A parent course $course\_i$. ($m \leq n$)

$i$-th course has:

1. Some lecture section(s) under it. (As mentioned above.)
2. A parent course category $category\_i$. ($t \leq m$)

Each student has ordered all $n$ sections from $1$ to $n$ on the basis of his/her preference.

Now, each student $i$ has to be allocated $q\_i$ ($2 \geq q\_i \geq 1$) sections such that:

1. No student has been allocated more than two or more section that have the same element(s) from $S$ associated with themselves. Formally, if the sets of lecture timings of allocated sections for a student $i$ are $T\_1$, $T\_2$, $\cdots$, $T\_{q\_i}$, then allocation should ensure that $|T\_1 \cup T\_2 \cup \cdots \cup T\_{q\_i}| = 2{q\_i}$.
2. No student has been allocated two or more sections which have the same parent course.
3. No student has been allocated more than $u$ sections which have a parent course which have the same course category. ($u \geq 1$) Formally, let $X$ be a list of $category\_{course\_{j}}$ where $j$ is any section allocated to a student. The frequency of any element in $X$ should not exceed $u$.
4. No section $j$ is allocated to more than $cap\_j$ students.
5. $\sum\_{j=1}^p cost(j)$ is minimized. $cost(x)$ is defined as the sum of positions of the $x$th student's allocated sections in his/her preference list. For example, a student had ordered the courses P, Q, R, S in the order: R, Q, S, P. If he/she was allocated Q and S, cost() function will return 5. (2+3)

Constraints:

* $1 \leq t \leq 7$
* $3 \leq m \leq 9$
* $5 \leq n \leq 30$
* $250 \leq p \leq 700$
* $\sum\_{i=1}^p q\_i \leq \sum\_{i=1}^n cap\_i$

**My take**

I tried to represent the problem in the form of a k-partite graph. Doing so would have helped implement network flow algorithms like minimum-cost, maximum-flow. However, I have not been able to come up with any representation that satisfies all of the given constraints.

# Answer
Timetabling is known to be NP-complete. Your more complex variant is too. Don't expect "nice" or "efficient" solutions. Either settle for an approximate solution (good luck in deriving one) or some sort of randomized heuristic.

I'd try some variant of genetic algorithms (look around for it's application to time tabling, they use special mutation and crossover operations that at least try to respect restrictions).
> 1 votes

---
Tags: algorithms, graphs, optimization, network-flow, bipartite-matching
---


# Question
Title: Where is the original literature for the specification of an Associative Array ADT?
I'm looking for the formal specification for the Abstract Data Type Algebra for the Associative Array, Associative List (AKA multimap), and other similar ADT to cite for use in a data specification similar to Binary JSON. The Wikipedia Associative Array entry uses non-standard math terminology and their sources are all secondary sources with no original sources. There is an algebra for the Dictionary and it starts with Let x be a set and it defines operations on that set. Who invented the dictionary and when? It should be pretty old, possible from the Journal of the Association of Computer Machinery or similar publication.

# Answer
> 1 votes
The consensus from the available information I've found points to SNOBOL4, released in 1967, as the earliest implementation of "associative arrays".

This post on the Software Engineering community is very similar to your question and has some great info.

> Associative arrays were first used in the programming language Snobol4 in the mid-1960s. They are a very common data structure in the Unix environment, being provided as the major data structure by languages like Awk, Perl, etc.

---
Tags: abstract-data-types
---


# Question
Title: What is the definition of P, NP, NP-complete and NP-hard?
I'm in a course about *computing* and *complexity*, and am unable to understand what these terms mean.

All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea what they actually mean. Wikipedia isn't much help either, as the explanations are still a bit too high level.

# Answer
> 462 votes
I think the Wikipedia articles $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{P}$ vs. $\mathsf{NP}$ are quite good. Still here is what I would say: Part I, Part II

\[I will use remarks inside brackets to discuss some technical details which you can skip if you want.\]

---

# Part I

### Decision Problems

There are various kinds of computational problems. However in an introduction to computational complexity theory course it is easier to focus on **decision problem**, i.e. problems where the answer is either YES or NO. There are other kinds of computational problems but most of the time questions about them can be reduced to similar questions about decision problems. Moreover decision problems are very simple. Therefore in an introduction to computational complexity theory course we focus our attention to the study of decision problems.

We can identify a decision problem with the subset of inputs that have answer YES. This simplifies notation and allows us to write $x\in Q$ in place of $Q(x)=YES$ and $x \notin Q$ in place of $Q(x)=NO$.

Another perspective is that we are talking about **membership queries** in a set. Here is an example:

**Decision Problem:**

> Input: A natural number $x$,
> Question: Is $x$ an even number?

**Membership Problem:**

> Input: A natural number $x$,
> Question: Is $x$ in $Even = \\{0,2,4,6,\cdots\\}$?

We refer to the YES answer on an input as **accepting** the input and to the NO answer on an input as **rejecting** the input.

We will look at **algorithms** for decision problems and discuss how efficient those algorithms are in their *usage of **computable resources***. I will rely on your intuition from programming in a language like C in place of formally defining what we mean by an algorithm and computational resources.

\[Remarks:

1. If we wanted to do everything formally and precisely we would need to fix a model of computation like the standard Turing machine model to *precisely* define what we mean by an algorithm and its usage of computational resources.
2. If we want to talk about computation over objects that the model cannot directly handle, we would need to encode them as objects that the machine model can handle, e.g. if we are using Turing machines we need to encode objects like natural numbers and graphs as binary strings.\]

---

### $\mathsf{P}$ = Problems with Efficient Algorithms for *Finding* Solutions

Assume that **efficient algorithms** means algorithms that use at most **polynomial** amount of computational resources. The main resource we care about is the worst-case **running time** of algorithms with respect to the input size, i.e. the number of basic steps an algorithm takes on an input of size $n$. The size of an input $x$ is $n$ if it takes $n$-bits of computer memory to store $x$, in which case we write $|x| = n$. So *by efficient algorithms we mean algorithms that have polynomial worst-case running time*.

The *assumption* that polynomial-time algorithms capture the intuitive notion of efficient algorithms is known as Cobham's thesis. I will not discuss at this point whether $\mathsf{P}$ is the right model for efficiently solvable problems and whether $\mathsf{P}$ does or does not capture what can be computed efficiently in practice and related issues. For now there are good reasons to make this assumption so for our purpose we assume this is the case. If you do not accept Cobham's thesis it does not make what I write below incorrect, the only thing we will lose is the *intuition* about efficient computation in practice. I think it is a helpful assumption for someone who is starting to learn about complexity theory.

> **$\mathsf{P}$ is the class of decision problems that can be solved efficiently**,
> i.e. decision problems which have polynomial-time algorithms.

More formally, we say a decision problem $Q$ is in $\mathsf{P}$ iff

> there is an efficient algorithm $A$ such that
> for all inputs $x$,
>
> * if $Q(x)=YES$ then $A(x)=YES$,
> * if $Q(x)=NO$ then $A(x)=NO$.

I can simply write $A(x)=Q(x)$ but I write it this way so we can compare it to the definition of $\mathsf{NP}$.

---

### $\mathsf{NP}$ = Problems with Efficient Algorithms for *Verifying* Proofs/Certificates/Witnesses

Sometimes we do not know any efficient way of finding the answer to a decision problem, however if someone tells us the answer and gives us a **proof** we can efficiently **verify** that the answer is correct by checking the proof to see if it is a **valid proof**. This is the idea behind the complexity class $\mathsf{NP}$.

If the proof is too long it is not really useful, it can take too long to just read the proof let alone check if it is valid. We want the time required for verification to be reasonable in the size of the original input, not the size of the given proof! This means what we really want is not arbitrary long proofs but *short* proofs. Note that if the verifier's running time is polynomial in the size of the original input then it can only read a polynomial part of the proof. So by *short* we mean *of polynomial size*.

From this point on whenever I use the word "proof" I mean "short proof".

Here is an example of a problem which we *do not know* how to solve efficiently but we can efficiently verify proofs:

> **Partition**
> **Input:** a finite set of natural numbers $S$,
> **Question:** is it possible to partition $S$ into two sets $A$ and $B$ ($A \cup B = S$ and $A \cap B = \emptyset$)
> such that the sum of the numbers in $A$ is equal to the sum of number in $B$ ($\sum\_{x\in A}x=\sum\_{x\in B}x$)?

If I give you $S$ and ask you if we can partition it into two sets such that their sums are equal, you do not know any efficient algorithm to solve it. You will probably try all possible ways of partitioning the numbers into two sets until you find a partition where the sums are equal or until you have tried all possible partitions and none has worked. If any of them worked you would say **YES**, otherwise you would say **NO**.

But there are *exponentially* many possible partitions so it will take a lot of time to enumerate all the possibilities. However if *I give you* two sets $A$ and $B$, you can easily check if the sums are equal and if $A$ and $B$ is a partition of $S$. Note that we can compute sums efficiently.

Here the pair of $A$ and $B$ that I give you is a proof for a YES answer. You can efficiently verify my claim by looking at my proof and checking if it is a **valid proof**. If the answer is YES then there is a valid proof, and I can give it to you and you can verify it efficiently. If the answer is NO then there is no valid proof. So whatever I give you you can check and see it is not a valid proof. I cannot trick you by an invalid proof that the answer is YES. Recall that if the proof is too big it will take a lot of time to verify it, we do not want this to happen, so we only care about *efficient* proofs, i.e. proofs which have polynomial size.

Sometimes people use "**certificate**" or "**witness**" in place of "proof".

Note I am giving you enough information about the answer for a given input $x$ so that you can find and verify the answer efficiently. For example, in our partition example I do not tell you the answer, I just give you a partition, and you can check if it is valid or not. Note that you have to verify the answer yourself, you cannot trust me about what I say. Moreover you can only check the correctness of *my* proof. If my proof is valid it means the answer is YES. But if my proof is invalid it does *not* mean the answer is NO. You have seen that one proof was invalid, not that there are no valid proofs. We are talking about proofs for YES. We are not talking about proofs for NO.

Let us look at an example: $A=\\{2,4\\}$ and $B=\\{1,5\\}$ is a proof that $S=\\{1,2,4,5\\}$ can be partitioned into two sets with equal sums. We just need to sum up the numbers in $A$ and the numbers in $B$ and see if the results are equal, and check if $A$, $B$ is partition of $S$.

If I gave you $A=\\{2,5\\}$ and $B=\\{1,4\\}$, you will check and see that my proof is invalid. It does not mean the answer is NO, it just means that this particular proof was invalid. Your task here is *not* to find the answer, but only to check if the proof you are given is valid.

It is like a student solving a question in an exam and a professor checking if the answer is correct. :) (unfortunately often students do not give enough information to verify the correctness of their answer and the professors have to guess the rest of their partial answer and decide how much mark they should give to the students for their partial answers, indeed a quite difficult task).

The amazing thing is that the same situation applies to many other natural problems that we want to solve: **we can efficiently *verify* if a given short proof is valid, but we do not know any efficient way of *finding* the answer**. This is the motivation why the complexity class $\mathsf{NP}$ is *extremely interesting* (though this was not the original motivation for defining it). Whatever you do (not just in CS, but also in math, biology, physics, chemistry, economics, management, sociology, business, ...) you will face computational problems that fall in this class. To get an idea of how many problems turn out to be in $\mathsf{NP}$ check out a compendium of NP optimization problems. Indeed you will have hard time finding natural problems which are not in $\mathsf{NP}$. It is simply amazing.

> **$\mathsf{NP}$ is the class of problems which have efficient verifiers**, i.e.
> there is a polynomial time algorithm that can verify if a given solution is correct.

More formally, we say a decision problem $Q$ is in $\mathsf{NP}$ iff

> there is an efficient algorithm $V$ called verifier such that
> for all inputs $x$,
>
> * if $Q(x)=YES$ then there is a proof $y$ such that $V(x,y)=YES$,
> * if $Q(x)=NO$ then for all proofs $y$, $V(x,y)=NO$.

We say a verifier is **sound** if it does not accept any proof when the answer is NO. In other words, a sound verifier cannot be tricked to accept a proof if the answer is really NO. No false positives.

Similarly, we say a verifier is **complete** if it accepts at least one proof when the answer is YES. In other words, a complete verifier can be convinced of the answer being YES.

The terminology comes from logic and **proof systems**. We cannot use a sound proof system to prove any false statements. We can use a complete proof system to prove all true statements.

The verifier $V$ gets two inputs,

* $x$ : the original input for $Q$, and
* $y$ : a suggested proof for $Q(x)=YES$.

Note that we want $V$ to be efficient in the size of $x$. If $y$ is a big proof the verifier will be able to read *only a polynomial part* of $y$. That is why we require the proofs to be short. If $y$ is short saying that $V$ is efficient in $x$ is the same as saying that $V$ is efficient in $x$ and $y$ (because the size of $y$ is bounded by a fixed polynomial in the size of $x$).

In summary, to show that a decision problem $Q$ is in $\mathsf{NP}$ we have to give an *efficient* verifier algorithm which is *sound* and *complete*.

Historical Note: historically this is not the original definition of $\mathsf{NP}$. The original definition uses what is called **non-deterministic** Turing machines. These machines do not correspond to any *actual* machine model and are difficult to get used to (at least when you are starting to learn about complexity theory). I have read that many experts think that they would have used the verifier definition as the main definition and even would have named the class $\mathsf{VP}$ (for verifiable in polynomial-time) in place of $\mathsf{NP}$ if they go back to the dawn of the computational complexity theory. The verifier definition is more natural, easier to understand conceptually, and easier to use to show problems are in $\mathsf{NP}$.

---

### $\mathsf{P}\subseteq \mathsf{NP}$

Therefore we have **$\mathsf{P}$=efficient solvable** and **$\mathsf{NP}$=efficiently verifiable**. So $\mathsf{P}=\mathsf{NP}$ iff the problems that can be efficiently verified are the same as the problems that can be efficiently solved.

Note that any problem in $\mathsf{P}$ is also in $\mathsf{NP}$, i.e. if you can solve the problem you can also verify if a given proof is correct: the verifier will just ignore the proof!

That is because we do not need it, the verifier can compute the answer by itself, it can decide if the answer is YES or NO without any help. If the answer is NO we know there should be no proofs and our verifier will just reject every suggested proof. If the answer is YES, there should be *a* proof, and in fact we will just accept anything as a proof.

\[We could have made our verifier accept only some of them, that is also fine, as long as our verifier accept at least one proof the verifier works correctly for the problem.\]

Here is an example:

> **Sum**
> **Input:** a list of $n+1$ natural numbers $a\_1,\cdots,a\_n$, and $s$,
> **Question:** is $\Sigma\_{i=1}^n a\_i = s$?

The problem is in $\mathsf{P}$ because we can sum up the numbers and then compare it with $s$, we return YES if they are equal, and NO if they are not.

The problem is also in $\mathsf{NP}$. Consider a verifier $V$ that gets a proof plus the input for Sum. It acts the same way as the algorithm in $\mathsf{P}$ that we described above. This is an efficient verifier for Sum.

Note that there are other efficient verifiers for Sum, and some of them might use the proof given to them. However the one we designed does not and that is also fine. Since we gave an efficient verifier for Sum the problem is in $\mathsf{NP}$. The same trick works for all other problems in $\mathsf{P}$ so $\mathsf{P} \subseteq \mathsf{NP}$.

---

### Brute-Force/Exhaustive-Search Algorithms for $\mathsf{NP}$ and $\mathsf{NP}\subseteq \mathsf{ExpTime}$

The best algorithms *we know of* for solving an arbitrary problem in $\mathsf{NP}$ are *brute-force*/*exhaustive-search* algorithms. Pick an efficient verifier for the problem (it has an efficient verifier by our assumption that it is in $\mathsf{NP}$) and check all possible proofs one by one. If the verifier accepts one of them then the answer is YES. Otherwise the answer is NO.

In our partition example, we try all possible partitions and check if the sums are equal in any of them.

Note that the brute-force algorithm runs in worst-case exponential time. The size of the proofs is polynomial in the size of input. If the size of the proofs is $m$ then there are $2^m$ possible proofs. Checking each of them will take polynomial time by the verifier. So in total the brute-force algorithm takes exponential time.

This shows that any $\mathsf{NP}$ problem can be solved in exponential time, i.e. $\mathsf{NP}\subseteq \mathsf{ExpTime}$. (Moreover the brute-force algorithm will use only a polynomial amount of space, i.e. $\mathsf{NP}\subseteq \mathsf{PSpace}$ but that is a story for another day).

A problem in $\mathsf{NP}$ can have much faster algorithms, for example any problem in $\mathsf{P}$ has a polynomial-time algorithm. However for an arbitrary problem in $\mathsf{NP}$ we do not know algorithms that can do much better. In other words, if you just tell me that your problem is in $\mathsf{NP}$ (and nothing else about the problem) then the fastest algorithm that we know of for solving it takes exponential time.

However it does not mean that there are not any better algorithms, *we do not know that*. As far as we know it is still possible (though thought to be very unlikely by almost all complexity theorists) that $\mathsf{NP}=\mathsf{P}$ and all $\mathsf{NP}$ problems can be solved in polynomial time.

Furthermore, some experts *conjecture* that we cannot do much better, i.e. there are problems in $\mathsf{NP}$ that cannot be solved much more efficiently than brute-force search algorithms which take exponential amount of time. See the Exponential Time Hypothesis for more information. But this is not proven, it is only a *conjecture*. It just shows how far we are from finding polynomial time algorithms for arbitrary $\mathsf{NP}$ problems.

This association with exponential time confuses some people: they think incorrectly that $\mathsf{NP}$ problems *require* exponential-time to solve (or even worse there are no algorithm for them at all). Stating that a problem is in $\mathsf{NP}$ does not mean a problem is *difficult* to solve, it just means that it is *easy* to verify, it is an *upper bound* on the difficulty of solving the problem, and many $\mathsf{NP}$ problems are easy to solve since $\mathsf{P}\subseteq\mathsf{NP}$.

Nevertheless, there are $\mathsf{NP}$ problems which *seem to* be hard to solve. I will return to this in when we discuss $\mathsf{NP}$-hardness.

---

## Lower Bounds *Seem* Difficult to Prove

OK, so we now know that there are many natural problems that are in $\mathsf{NP}$ and we do not know any efficient way of solving them and we suspect that they really require exponential time to solve. Can we prove this?

Unfortunately the task of proving **lower bounds** is very difficult. We *cannot* even prove that these problems require more than *linear time*! Let alone requiring exponential time.

Proving linear-time lower bounds is rather easy: the algorithm needs to read the input after all. Proving super-linear lower bounds is a completely different story. We can prove super-linear lower bounds with more restrictions about the kind of algorithms we are considering, e.g. sorting algorithms using comparison, but we do not know lower-bounds without those restrictions.

To prove an upper bound for a problem we just need to design a good enough algorithm. It often needs knowledge, creative thinking, and even ingenuity to come up with such an algorithm.

However the task is considerably simpler compared to proving a lower bound. We have to show that *there are no good algorithms*. Not that we do not *know of* any good enough algorithms right now, but that *there does not exist any good algorithms*, that *no one will ever come up with a good algorithm*. Think about it for a minute if you have not before, how can we show such an **impossibility result**?

This is another place where people get confused. Here "impossibility" is a **mathematical impossibility**, i.e. it is not a short coming on our part that some genius can fix in future. When we say impossible we mean it is absolutely impossible, as impossible as $1=0$. No scientific advance can make it possible. That is what we are doing when we are proving lower bounds.

To prove a lower bound, i.e. to show that a problem *requires* some amount of time to solve, means that we have to prove that *any* algorithm, even very ingenuous ones that do not know yet, cannot solve the problem faster. There are many intelligent ideas that we know of (greedy, matching, dynamic programming, linear programming, semidefinite programming, sum-of-squares programming, and many other intelligent ideas) and there are many many more that we do not know of yet. Ruling out one algorithm or one particular idea of designing algorithms is not sufficient, we need to rule out all of them, even those we do not know about yet, even those may not ever know about! And one can combine all of these in an algorithm, so we need to rule out their combinations also. There has been some progress towards showing that some ideas cannot solve difficult $\mathsf{NP}$ problems, e.g. greedy and its extensions cannot work, and there are some work related to dynamic programming algorithms, and there are some work on particular ways of using linear programming. But these are not even close to ruling out the intelligent ideas that we know of (search for lower-bounds in restricted models of computation if you are interested).

---

## Barriers: Lower Bounds *Are* Difficult to Prove

On the other hand we have mathematical results called barriers that say that a lower-bound proof cannot be such and such, and such and such almost covers all techniques that we have used to prove lower bounds! In fact many researchers gave up working on proving lower bounds after Alexander Razbarov and Steven Rudich's natural proofs barrier result. It turns out that the existence of particular kind of lower-bound proofs would imply the insecurity of cryptographic pseudorandom number generators and many other cryptographic tools.

I say almost because in recent years there has been some progress mainly by Ryan Williams that has been able to intelligently circumvent the barrier results, still the results so far are for very weak models of computation and quite far from ruling out general polynomial-time algorithms.

But I am diverging. The main point I wanted to make was that proving lower bounds is difficult and we do not have strong lower bounds for general algorithms solving $\mathsf{NP}$ problems.

\[On the other hand, Ryan Williams' work shows that there are close connections between proving lower bounds and proving upper bounds. See his talk at ICM 2014 if you are interested.\]

---

## Reductions: Solving a Problem Using Another Problem as a Subroutine/Oracle/Black Box

The idea of a reduction is very simple: to solve a problem, use an algorithm for another problem.

Here is simple example: assume we want to compute the sum of a list of $n$ natural numbers and we have an algorithm $\operatorname{Sum}$ that returns the sum of two given numbers. Can we use $\operatorname{Sum}$ to add up the numbers in the list? Of course!

**Problem:**

> Input: a list of $n$ natural numbers $x\_1,\ldots,x\_n$,
> Output: return $\sum\_{i=1}^{n} x\_i$.

**Reduction Algorithm:**

> 1. $s = 0$
> 2. for $i$ from $1$ to $n$
> 2.1. $s = \operatorname{Sum}(s,x\_i)$
> 3. return $s$

Here we are using $\operatorname{Sum}$ in our algorithm as a **subroutine**. Note that we do not care about how $\operatorname{Sum}$ works, it acts like **black box** for us, we do not care what is going on inside $\operatorname{Sum}$. We often refer to the subroutine $\operatorname{Sum}$ as **oracle**. It is like the oracle of Delphi in Greek mythology, we ask questions and the oracle answers them and we use the answers.

This is essentially what a reduction is: assume that we have algorithm for a problem and use it as an oracle to solve another problem. Here efficient means efficient assuming that the oracle answers in a unit of time, i.e. we count each execution of the oracle a single step.

If the oracle returns a large answer we need to read it and that can take some time, so we should count the time it takes *us* to read the answer that oracle has given to us. Similarly for writing/asking the question from the oracle. But oracle works instantly, i.e. as soon as we ask the question from the oracle the oracle writes the answer for us in a single unit of time. All the work that oracle does is counted a single step, but this excludes the time it takes us to write the question and read the answer.

Because we do not care how oracle works but only about the answers it returns we can make a simplification and consider the oracle to be the problem itself in place of an algorithm for it. In other words, we do not care if the oracle is not an algorithm, we do not care how oracles comes up with its replies.

For example, $\operatorname{Sum}$ in the question above is the addition function itself (not an algorithm for computing addition).

We can ask multiple questions from an oracle, and the questions does not need to be predetermined: we can ask a question and based on the answer that oracle returns we perform some computations by ourselves and then ask another question based on the answer we got for the previous question.

Another way of looking at this is thinking about it as an **interactive computation**. Interactive computation in itself is large topic so I will not get into it here, but I think mentioning this perspective of reductions can be helpful.

An algorithm $A$ that uses a oracle/black box $O$ is usually denoted as $A^O$.

The reduction we discussed above is the most general form of a reduction and is known as **black-box reduction** (a.k.a. **oracle reduction**, **Turing reduction**).

More formally:

> We say that problem $Q$ is black-box reducible to problem $O$ and write $Q \leq\_T O$ iff
> there is an algorithm $A$ such that for all inputs $x$,
> $Q(x) = A^O(x)$.

In other words if there is an algorithm $A$ which uses the oracle $O$ as a subroutine and solves problem $Q$.

If our reduction algorithm $A$ runs in polynomial time we call it a **polynomial-time black-box reduction** or simply a **Cook reduction** (in honor of Stephen A. Cook) and write $Q\leq^\mathsf{P}\_T O$. (The subscript $T$ stands for "Turing" in the honor of Alan Turing).

However we may want to put some restrictions on the way the reduction algorithm interacts with the oracle. There are several restrictions that are studied but the most useful restriction is the one called **many-one reductions** (a.k.a. **mapping reductions**).

The idea here is that on a given input $x$, we perform some polynomial-time computation and generate a $y$ that is an instance of the problem the oracle solves. We then ask the oracle and return the answer it returns to us. We are allowed to ask a single question from the oracle and the oracle's answers is what will be returned.

More formally,

> We say that problem $Q$ is many-one reducible to problem $O$ and write $Q \leq\_m O$ iff
> there is an algorithm $A$ such that for all inputs $x$,
> $Q(x) = O(A(x))$.

When the reduction algorithm is polynomial time we call it **polynomial-time many-one reduction** or simply **Karp reduction** (in honor of Richard M. Karp) and denote it by $Q \leq\_m^\mathsf{P} O$.

The main reason for the interest in this particular non-interactive reduction is that it preserves $\mathsf{NP}$ problems: if there is a polynomial-time many-one reduction from a problem $A$ to an $\mathsf{NP}$ problem $B$, then $A$ is also in $\mathsf{NP}$.

The simple notion of reduction is one of the most fundamental notions in complexity theory along with $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{NP}$-complete (which we will discuss below).

---

**The post has become too long and exceeds the limit of an answer (30000 characters). I will continue the answer in Part II.**

# Answer
> 229 votes
# Part II

Continued from Part I.

The previous one exceeded the maximum number of letters allowed in an answer (30000) so I am breaking it in two.

## $\mathsf{NP}$-completeness: *Universal* $\mathsf{NP}$ Problems

OK, so far we have discussed the class of efficiently solvable problems ($\mathsf{P}$) and the class of efficiently verifiable problems ($\mathsf{NP}$). As we discussed above, both of these are *upper-bounds*. Let's focus our attention for now on problems inside $\mathsf{NP}$ as amazingly many natural problems turn out to be inside $\mathsf{NP}$.

Now sometimes we want to say that *a problem is difficult to solve*. But as we mentioned above we cannot use lower-bounds for this purpose: theoretically they are exactly what we would like to prove, however in practice we have not been very successful in proving lower bounds and in general they are hard to prove as we mentioned above. Is there still a way to say that *a problem is difficult to solve*?

Here comes the notion of $\mathsf{NP}$-completeness. But before defining $\mathsf{NP}$-completeness let us have another look at reductions.

### Reductions as *Relative Difficulty*

We can think of **lower-bounds as absolute difficulty** of problems. Then we can think of **reductions as relative difficulty** of problems. We can take *a reductions from $A$ to $B$* as saying *$A$ is easier than $B$*. This is implicit in the $\leq$ notion we used for reductions. Formally, reductions give partial orders on problems.

If we can efficiently reduce a problem $A$ to another problem $B$ then $A$ should not be more difficult than $B$ to solve. The intuition is as follows:

Let $M^B$ be an efficient reduction from $A$ to $B$, i.e. $M$ is an efficient algorithm that uses $B$ and solves $A$. Let $N$ be an efficient algorithm that solves $B$. We can combine the efficient reduction $M^B$ and the efficient algorithm $N$ to obtain $M^N$ which is an efficient algorithm that solves $A$.

This is because we can use an efficient subroutine in an efficient algorithm (where each subroutine call costs one unit of time) and the result is an efficient algorithm. This is a very nice closure property of polynomial-time algorithms and $\mathsf{P}$, it does not hold for many other complexity classes.

### $\mathsf{NP}$-complete means most difficult $\mathsf{NP}$ problems

Now that we have a relative way of comparing difficulty of problems we can ask which problems are most difficult among problems in $\mathsf{NP}$? We call such problems *$\mathsf{NP}$-complete*.

> **$\mathsf{NP}$-complete problems are the most difficult $\mathsf{NP}$ problems**,
> if we can solve an $\mathsf{NP}$-complete problem efficiently, we can solve all $\mathsf{NP}$ problems efficiently.

More formally, we say a decision problem $A$ is $\mathsf{NP}$-complete iff

> $A$ is in $\mathsf{NP}$, and
> for all $\mathsf{NP}$ problems $B$, $B$ is polynomial-time many-one reducible to $A$ ($B\leq\_m^\mathsf{P} A$).

Another way to think about $\mathsf{NP}$-complete problems is to think about them as the complexity version of universal Turing machines. An $\mathsf{NP}$-complete problem is **universal** among $\mathsf{NP}$ problems in a similar sense: you can use them to solve any $\mathsf{NP}$ problem.

This is one of the reasons that good SAT-solvers are important, particularly in the industry. SAT is $\mathsf{NP}$-complete (more on this later), so we can focus on designing very good algorithms (as much as we can) for solving SAT. To solve any other problem in $\mathsf{NP}$ we can convert the problem instance to a SAT instance and then use an industrial-quality highly-optimized SAT-solver.

(Two other problems that lots of people work on optimizing their algorithms for them for practical usage in industry are Integer Programming and Constraint Satisfaction Problem. Depending on your problem and the instances you care about the optimized algorithms for one of these might perform better than the others.)

If a problem satisfies the second condition in the definition of $\mathsf{NP}$-completeness (i.e. the universality condition)
we call the problem *$\mathsf{NP}$-hard*.

$\mathsf{NP}$-hardness is a way of saying that a problem is difficult.

I personally prefer to think about $\mathsf{NP}$-hardness as universality, so probably *$\mathsf{NP}$-universal* could have been a more correct name, since we do not know at the moment if they are really hard or it is just because we have not been able to find a polynomial-time algorithm for them).

The name $\mathsf{NP}$-hard also confuses people to incorrectly think that $\mathsf{NP}$-hard problems are problems which are *absolutely* hard to solve. We do not know that yet, we only know that they are *as difficult as any $\mathsf{NP}$ problem* to solve. Though experts think it is unlikely it is still possible that all $\mathsf{NP}$ problems are easy and efficiently solvable. In other words, being as difficult as any other $\mathsf{NP}$ problem does not mean really difficult. That is only true if there is an $\mathsf{NP}$ problem which is *absolutely* hard (i.e. does not have any polynomial time algorithm).

Now the questions are:

* Are there any $\mathsf{NP}$-complete problems?
* Do we know any of them?

I have already given away the answer when we discussed SAT-solvers. The surprising thing is that many natural $\mathsf{NP}$ problems turn out to be $\mathsf{NP}$-complete (more on this later). So if we randomly pick a natural problems in $\mathsf{NP}$, with very high probability it is either that we know a polynomial-time algorithm for it or that we know it is $\mathsf{NP}$-complete. The number of natural problems which are not known to be either is quite small (an important example is factoring integers, see this list for a list of similar problems).

Before moving to examples of $\mathsf{NP}$-complete problems, note that we can give similar definitions for other complexity classes and define complexity classes like $\mathsf{ExpTime}$-complete. But as I said, $\mathsf{NP}$ has a very special place: unlike $\mathsf{NP}$ other complexity classes have few natural complete problems.

(By a natural problem I mean a problem that people really care about solving, not problems that are defined artificially by people to demonstrate some point. We can modify any problem in a way that it remains essentially the same problem, e.g. we can change the answer for the input $p \lor \lnot p$ in SAT to be NO. We can define infinitely many distinct problems in a similar way without essentially changing the problem. But who would really care about these artificial problem by themselves?)

## $\mathsf{NP}$-complete Problems: There are Universal Problems in $\mathsf{NP}$

First, note that if $A$ is $\mathsf{NP}$-hard and $A$ polynomial-time many-one reduces to $B$ then $B$ is also $\mathsf{NP}$-hard. We can solve any $\mathsf{NP}$ problem using $A$ and we can solve $A$ itself using $B$, so we can solve any $\mathsf{NP}$ problem using $B$!

This is a very useful lemma. If we want to show that a problem is $\mathsf{NP}$-hard we have to show that we can reduce all $\mathsf{NP}$ problems to it, that is not easy because we know nothing about these problems other than that they are in $\mathsf{NP}$.

Think about it for a second. It is quite amazing the first time we see this. We can prove all $\mathsf{NP}$ problems are reducible to SAT and without knowing anything about those problems other than the fact that they are in $\mathsf{NP}$!

Fortunately we do not need to carry out this more than once. Once we show a problem like $SAT$ is $\mathsf{NP}$-hard for other problems we only need to reduce $SAT$ to them. For example, to show that $SubsetSum$ is $\mathsf{NP}$-hard we only need to give a reduction from $SAT$ to $SubsetSum$.

OK, let's show there is an $\mathsf{NP}$-complete problem.

### Universal Verifier is $\mathsf{NP}$-complete

**Note:** *the following part might be a bit technical on the first reading.*

The first example is a bit artificial but I think it is simpler and useful for intuition. Recall the verifier definition of $\mathsf{NP}$. We want to define a problem that can be used to solve all of them. So why not just define the problem to be that?

> **Time-Bounded Universal Verifier**
> Input: the code of an algorithm $V$ which gets an input and a proof, an input $x$, and two numbers $t$ and $k$.
> Output: $YES$ if there is a proof of size at most $k$ s.t. it is accepted by $V$ for input $x$ in $t$-steps, $NO$ if there are no such proofs.

It is not difficult to show this problem which I will call $UniVer$ is $\mathsf{NP}$-hard:

> Take a verifier $V$ for a problem in $\mathsf{NP}$. To check if there is proof for given input $x$, we pass the code of $V$ and $x$ to $UniVer$.
> ($t$ and $k$ are upper-bounds on the running time of $V$ and the size of proofs we are looking for $x$. we need them to limit the running-time of $V$ and the size of proofs by polynomials in the size of $x$.)

(Technical detail: the running time will be polynomial in $t$ and we would like to have the size of input be at least $t$ so we give $t$ in unary notation not binary. Similar $k$ is given in unary.)

We still need to show that the problem itself is in $\mathsf{NP}$. To show the $UniVer$ is in $\mathsf{NP}$ we consider the following problem:

> **Time-Bounded Interpreter**
> Input: the code of an algorithm $M$, an input $x$ for $M$, and a number $t$.
> Output: $YES$ if the algorithm $M$ given input $x$ returns $YES$ in $t$ steps, $NO$ if it does not return $YES$ in $t$ steps.

You can think of an algorithm roughly as the code of a $C$ program. It is not difficult to see this problem is in $\mathsf{P}$. It is essentially writing an interpreter, counting the number of steps, and stopping after $t$ steps.

I will use the abbreviation $Interpreter$ for this problem.

Now it is not difficult to see that $UniVer$ is in $\mathsf{NP}$: given input $M$, $x$, $t$, and $k$; and a suggested proof $c$; check if $c$ has size at most $k$ and then use $Interpreter$ to see if $M$ returns $YES$ on $x$ and $c$ in $t$ steps.

### $SAT$ is $\mathsf{NP}$-complete

The universal verifier $UniVer$ is a bit artificial. It is not very useful to show other problems are $\mathsf{NP}$-hard. Giving a reducing from $UniVer$ is not much easier than giving a reduction from an arbitrary $\mathsf{NP}$ problem. We need problems which are simpler.

Historically the first natural problem that was shown to be $\mathsf{NP}$-complete was $SAT$.

Recall that $SAT$ is the problem where we are given a propositional formula and we want to see if it is *satisfiable*, i.e. if we can assign true/false to the propositional variables to make it evaluate to true.

> **SAT**
> Input: a propositional formula $\varphi$.
> Output: $YES$ if $\varphi$ is satisfiable, $NO$ if it is not.

It is not difficult to see that $SAT$ is in $\mathsf{NP}$. We can evaluate a given propositional formula on a given truth assignment in polynomial time. The verifier will get a truth assignment and will evaluate the formula on that truth assignment.

---

To be written...

SAT is $\mathsf{NP}$-hard

## What does $\mathsf{NP}$-completeness mean for practice?

## What to do if you *have to* solve an $\mathsf{NP}$-complete problem?

## $\mathsf{P}$ vs. $\mathsf{NP}$

## What's Next? Where To Go From Here?

# Answer
> 31 votes
More than useful mentioned answers, I recommend you **highly** to watch "**Beyond Computation: The P vs NP Problem**" by **Michael Sipser**. I think this video should be archived as one of the leading teaching video in computer science.!

Enjoy!

# Answer
> 14 votes
Simplest of them is P, problems solvable in polynomial time belongs here.

Then comes NP. Problems solvable in polynomial time on a non-deterministic Turing machine belongs here.

The hardness and completeness has to with reductions. A problem A is *hard* for a class C if every problem in C reduces to A. If problem A is *hard for NP*, or NP-hard, if every problem in NP reduces to A.

Finally, a problem is *complete* for a class C if it is *in* C and *hard* for C. In your case, problem A is *complete for NP*, or NP-complete, if every problem in NP reduces to A, and A is in NP.

To add to explanation of NP, a problem is in NP if and only if a solution can be verified in (deterministic) polynomial time. Consider any NP-complete problem you know, SAT, CLIQUE, SUBSET SUM, VERTEX COVER, etc. If you "get the solution", you can verify its correctness in polynomial time. They are, resp., truth assignments for variables, complete subgraph, subset of numbers and set of vertices that dominates all edges.

# Answer
> 14 votes
Copying my answer to a similar question on Stack Overflow:

The easiest way to explain P v. NP and such without getting into technicalities is to compare "word problems" with "multiple choice problems".

When you are trying to solve a "word problem" you have to find the solution from scratch. When you are trying to solve a "multiple choice problems" you have a choice: either solve it as you would a "word problem", or try to plug in each of the answers given to you, and pick the candidate answer that fits.

It often happens that a "multiple choice problem" is much easier than the corresponding "word problem": substituting the candidate answers and checking whether they fit may require significantly less effort than finding the right answer from scratch.

Now, if we would agree the effort that takes polynomial time "easy" then the class P would consist of "easy word problems", and the class NP would consist of "easy multiple choice problems".

The essence of P v. NP is the question: "Are there any easy multiple choice problems that are not easy as word problems"? That is, are there problems for which it's easy to verify the validity of a given answer but finding that answer from scratch is difficult?

Now that we understand intuitively what NP is, we have to challenge our intuition. It turns out that there are "multiple choice problems" that, in some sense, are hardest of them all: if one would find a solution to one of those "hardest of them all" problems one would be able to find a solution to ALL NP problems! When Cook discovered this 40 years ago it came as a complete surprise. These "hardest of them all" problems are known as NP-hard. If you find a "word problem solution" to one of them you would automatically find a "word problem solution" to each and every "easy multiple choice problem"!

Finally, NP-complete problems are those that are simultaneously NP and NP-hard. Following our analogy, they are simultaneously "easy as multiple choice problems" and "the hardest of them all as word problems".

# Answer
> 12 votes
From the P vs. NP and the Computational Complexity Zoo video.

## For a computer with a *really big* version of a problem...

### **P problems**

*easy* to solve (rubix cube)

### **NP problems**

*hard* to solve - but checking answers is *easy* (sudoku)

Perhaps these are all really P problems but we don't know it... **P vs. NP**.

**NP-complete**

Lots of NP problems boil down to the same one (sudoku is a newcomer to the list).

### **EXP problems**

*really hard* to solve (e.g. best next move in chess)

### **NP-hard problems**

NP-hard isn't well explained in the video (it's all the pink bits in the below diagram). Wikipedia's NP-hard Euler diagram is clearer on this.

## Diagram

As displayed near the end of the video.

# Answer
> 9 votes
**P**, **NP**, **NP-complete** and **NP-hard** are complexity classes, classifying problems according to the algorithmic complexity for solving them. In short, they're based on three properties:

**Solvable in polynomial time:** Defines decision problems that can be solved by a deterministic Turing machine (DTM) using a polynomial amount of computation time, i.e., its running time is upper bounded by a polynomial expression in the size of the input for the algorithm. Using Big-O notation this time complexity is defined as `O(n ^ k)`, where n is the size of the input and k a constant coefficient.

**Solution verifiable in polynomial time:** Defines decision problems for which a given solution can be verified by a DTM using a polynomial amount of computation time, even though obtaining the correct solution may require higher amounts of time.

**Reduces any NP problem in polynomial time**: Defines decision problems whose algorithms for solving them can be used to solve any NP problem after a polynomial time translation step.

---

I've recently written an article about this subject providing more details, including a code demonstration for reducing an NP problem into an NP-hard problem: Complexity classes of problems

---
Tags: complexity-theory, terminology, complexity-classes, p-vs-np, reference-question
---


# Question
Title: Recurrence Relation of Ternary search and the number of comparisons with binary search
i was reading the binary search and ternary search algorithms. But i had a doubt with recurrence relation of ternary search as somewhere it is **T(n/3)+c and T(2\*n/3)+c**. I want to know which one is correct as solution for both is same.

i have referred  and  and both are different. Which one is True and HOW???

Also the number of comparison in binary search is logn+1,So what is the number of comparisons in Ternary search and how?please elaborate it

# Answer
> 0 votes
You could do ternary search by splitting into three parts, use one comparison to see if the key has to be in the first third, and another one to distinguish between second and third stretch if it isn't in the first one. Assuming uniformly distributed searches, this would reduce the range to a third with $1/3 + 2 \cdot 2/3 = 5/3$ comparisons. This idea leads to $T(n) = T(n/3) + c$ (approximately).

Another idea would be to split in three, with one comparison check if it is in the first third, and continue recursively with the part containing the key. This leads to $T(n) = 1/3 T(n/3) + 2/3 T(2 n /3) + c$ (again a rough approximation to the real recurrence).

---
Tags: algorithms, search-algorithms, comparison
---


title: "Fuzzy" Chinese Remainder Theorem

text:
# Question
Title: "Fuzzy" Chinese Remainder Theorem
I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a\_1 \mod 3 \text{ with } a\_1 \in \\{0,1\\},\\ x&\equiv a\_2\mod 5 \text{ with } a\_2 \in \\{2,3,4\\},\\x&\equiv a\_3 \mod 7 \text{ with } a\_3 \in \\{5,6\\}\\ \end{align} These example moduli would provide a unique solution for $x \mod lcm(3,5,7)$, if the $a\_i$ were fixed. Because the $a\_i$ are not fixed, these "fuzzy" congruences lead to $2\*3\*2=12$ possible solutions for $x \mod lcm(3,5,7)$.

To reduce the number of possible solutions for $x$, there exists an additional condition, which provides an upper bound for $x$. For example: \begin{align} x \mod lcm(3\*5\*7) &\< 5 \end{align}

We can assume that all moduli $m\_i$ are primes, f.e. $lcm(m\_1,m\_2,...) = \prod\_i m\_i$. Furthermore each $a\_i$ has at most $t$ possible values ($t=3$ in the upper example). Additionally, the possible values of $a\_i$ are consecutive ($a\_2 \in \\{1,3,4\\}$ is not allowed). So the generic equations look like: \begin{align} x&\equiv a\_i \mod m\_i &\text{ with } a\_i \in U\_i \text{ and } U\_i \subset \\{0,1,...,m\_i-1\\} \wedge |U\_i| = t \wedge \\\&&\forall i,j: |i-j|=1 \Rightarrow |U\_i\[i\]-U\_i\[j\]| = 1 \\ x \mod \prod\_i m\_i &\< k \end{align}

Is it partical feasible to calculate **one** solution for parameters like $\prod\_i m\_i \approx 10^{1000}$, all $m\_i \< 100000$, $k \approx 10^{50}$ and $t \approx 50$?

I tried to use the Chinese Remainder Theorem Method to find a solution for x:

Set $M\_i:=lcm(m\_1,m\_2,...)/m\_i$. It holds $gcd(M\_i,m\_i)=1$.

Hence, we can use the Extended Euclidean algorithm to find 2 Integers $r\_i$ und $s\_i$, which fulfill $r\_i \cdot m\_i + s\_i \cdot M\_i = 1$.

Set $e\_i:=s\_i \cdot M\_i$, then \begin{align} e\_i &\equiv 1 \mod m\_i \\ e\_i &\equiv 0 \mod m\_j, j \neq i\end{align}.

The number $x:=\sum\_{i=1}^n a\_i \cdot e\_i \mod lcm(m\_1,m\_2,...)$ is a solution.

Now i tried to solve $(\sum\_{i=1}^n a\_i \cdot e\_i \mod \prod\_i m\_i) \< k$ with $minValue(U\_i) \<= a\_i \<= maxValue(U\_i)$.

These equations can be formulated as an Integer Programming instance (add an additional variable for the mod Operation). I tried to use mathematica to solve these, but it seems unfeasible even for "small" parameters like $\prod\_i m\_i \approx 10^{50}$, all $m\_i \< 1000$, $k \approx 10^{2}$ and $t = 3$.

Is there a more efficent way to solve this?

# Answer
This problem can be approached with the Coppersmith method. For details, see my answer at MO to a similar question.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: What is meant by a preemptive algorithm?
The definition on Google says 'serving or intended to pre-empt or forestall something, especially to prevent attack by disabling the enemy.' So, how does this relate to an algorithm, especially the Nearest Neighbour Algorithm?

# Answer
> 2 votes
An arbitrary algorithm can't be preemptive or non-preemptive. Preemption is a mode of multitasking, used by an operating system to control user processes. From the Preemption Wiki page:

> In computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time.

The opposite of Preemption is Cooperative Multitasking.

---
Tags: algorithms, heuristics
---


# Question
Title: How do i tell if a grammar is regular or not?
I know that a regular grammar has a definition

$$\begin{align}S &\to aS\\ S &\to \lambda \end{align}$$

But I dont really know how to apply this information to check whether or not a grammar is regular...

So for example I have a grammar $$\begin{align}S &\to aSbSb\\ S &\to \lambda \end{align}$$

If I compare it to the definition of a regular grammar this is not a regular grammar right? Which also means that I can't turn this into a regex.

Also could you please give me an example of a regular grammar and a non-regular grammar hopefully that will solidify my understanding.

# Answer
It's important to distinguish between regular *grammars* and regular *languages*.

Your first grammar is regular.

A regular grammar is either a right-regular grammar or a left-regular grammar. In a right-regular grammar, every production's right-hand side has at most one non-terminal, and that non-terminal is the last symbol in the right-hand side. A left-regular grammar is the same except that all the non-terminals are at the beginning of their respective right-hand sides.

As you observe, your second grammar is not a regular grammar, since there is a right-hand side with more than one non-terminal.

A regular *language* is a language for which a regular grammar exists. That's a much trickier criterion, since the fact that a particular grammar is not regular does not in any way prove anything about the regularity of the language generated by that grammar. The language might or might not be regular, and there is no algorithm which will even tell you for sure.

So your statement *"Which also means that I can't turn this into a regex."* does not follow. As it happens, your second grammar does not generate a regular language, but many non-regular grammars do recognise regular languages. Here's a simple example:

$$\begin{align}S &\to aS\\ S &\to Sb\\ S &\to \lambda \end{align}$$

That grammar generates the language $a^\*b^\*$, which is certainly a regular language. But this particular grammar is not regular because one production is left recursive and the other production is right recursive; in a regular grammar, either all productions with a non-terminal are left-regular, or all productions with a non-terminal are right-regular.
> 9 votes

# Answer
You are correct that the grammar $S \rightarrow aS \mid \lambda$ is regular. However, there are a *lot* of regular languages out there (a countably infinite number in fact!), so even if your grammar doesn't look like this, it can still be a regular language.

The standard way to show that a language is regular is to write a regular expression for it (or build a NFA, etc). And the standard way to show that a language is *not* regular is to use the Pumping Lemma.

But, the Pumping Lemma doesn't always work. And is kind of a pain in the ass to use. So instead, this is the Distinguishable Prefix Lemma, an alternate way to show non-regularity:

> Let $X$ be a set of strings. If, for any two distinct strings $x\_1$ and $x\_2$ in $X$, you can come up with some string $y$ such that $x\_1y$ is in your language and $x\_2y$ is not, then $X$ is called a *distinguishable prefix set*.
>
> If you can find an infinite distinguishable prefix set, then your language is not regular.

Write out some example strings in the language, and try to solve this yourself, using this lemma, before reading further!

---

You may have noticed that the string $a^i b^j$ is in the language, if and only if $j=2i$. (This doesn't cover the *entire* language, but that doesn't matter for this proof.)

So let's make $X$ be $a^i$ (for all natural $i$). Now, take two arbitrary distinct members from this set; let's say that $x\_1 = a^n$ and $x\_2 = a^m$, for arbitrary $n \neq m$.

Set $y = b^{2n}$. Now $x\_1y = a^nb^{2n}$ is in the language, and $x\_2y = a^mb^{2n}$ is not. And there are infinite natural numbers.

Therefore $X$ is a distinguishable prefix set, and has infinite members. So your language is **not regular**.

P.S. What I call the "Distinguishable Prefix Lemma" is a special case of the Myhill-Nerode Theorem, which is *stronger* than the Pumping Lemma! I'm not sure Myhill and Nerode used this name for the lemma, but it's what I learned, so I'm sticking to it.

Myhill-Nerode can actually show that a language *is* regular, too, but it's usually way more difficult in that direction. So you'll probably only want to use this method to show that something is *not* regular, not that it *is*.
> 3 votes

---
Tags: regular-languages, formal-grammars, regular-expressions
---


title: Problem in downvote system

text:
# Question
Title: Problem in downvote system
# Problem

For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated based on the total weight of the active players, and banned players cannot vote, so the total weight of the system can change during the computation.

Can I make this computation, avoiding infinite loops?

# Constraints

* The whole system is unveiled simultaneously, players and votes.
* I have to compute this on the fly, so I cannot fix the total weight by using the final weight of a previous computation
* I absolutely cannot count the banned players' votes, trolls are common
* Also because trolls are common, a big percentage of the players can be banned at any point, so I can't either just count them in the final weight even if their actual votes don't count, because the minimum downvote percentage by legit players can grow beyond 100%.

# Cases

I already spotted the trivial case of a player with 66%+ weight voting himself down, resembling *"this sentence is false"*, so I disabled that.

But there's also the case where there's N players that together account for 66%+ weight, and where every combination of N-1 players still account for 66%+, and each of those agents downvote each other. So together they downvote each other but at the same time, because all of them are downvoted, all of their votes don't count. It's almost the same as the previous case but way harder to solve and even detect.

However, I think that case is unlikely because most of the players have to conspire for that to happen, or just by chance which is even more unlikely I believe.

# Answer
> 1 votes
I come from a database / transaction background which will influence this answer.

My take would be to serialize the downvotes and handle one at a time. The banned function will be handled this way. Unbanning (is this a Word? ) will need to be handle separately: imagine that a troll is banned, a while later the total weight has increased enough for that player to be undammed.

1. When a player does a downvote, add the downvote to a queue (or similar). Save the id of the downvoted player, the id of the downvoter and the downvote quotient = downvoter current weight divided by current total weight.
2. In the serial function handle one item from the queue at a time.
3. Link the downvote to a list for the downvoted person. If one downvoter has downvoted a person several times, save only the latest. If the downvote player is already banned, nothing more needs to be done.
4. Now calculate the total downvote quotient by traversing the list. Only sum quotient for currently not banned users.
5. If the quotient is above 66% ban the user.
6. Take next item from the queue, see above

Now in order to unban a user you need to have a separate function. It might be a good idea to remove all old downvotes Before unbanning, or perhaps mark them as invalid?

---
Tags: algorithms, computability, combinatorics
---


# Question
Title: Is the P vs NP problem, an NP or co-NP problem?
A few years ago, a youtube channel named hackerdashery, made an extraordinary youtube video explaining **P vs NP**, in a semi-vulgarized way : https://www.youtube.com/watch?v=YX40hbAHx3s

At 7 minutes and 56 seconds however, he talks about why it is so hard to prove that **P $=$ NP** or that **P $\neq$ NP**, and states that proving things **is** in fact an **NP** problem (in the video however, he writes down that it is actually a **co-NP** problem).

Thus, is proving things, in particular **P $=$ NP** or **P $\neq$ NP**, an **NP** or **co-NP** problem? If so, why? And where could I find more on this?

# Answer
> 0 votes
Theorem-proving is **co-NP-complete** :

> Depending on the underlying logic, the problem of deciding the validity of a formula varies from trivial to impossible. For the frequent case of propositional logic, the problem is decidable but **co-NP-complete**, ...
> \- https://en.wikipedia.org/wiki/Automated\_theorem\_proving

In a comment, Yuval Filmus did state that the language of propositional tautologies is **co-NP-complete**, which basically is the same thing, since :

> "The most common type of mathematical theorem can be symbolized as p⟹q, where p and q may be compounded statements. To assert that p⟹q is a theorem is to claim that p⟹q is a tautology; that is, that it is always true. We know that p⟹q is true unless p is true and q is false. Thus, to prove that p implies q, we have to show that whenever p is true it follows that q must be true."
> \- https://math.stackexchange.com/questions/2486302/how-are-theorems-tautologies

I don't know how the problem of **P** versus **NP** could be described as propositional logic though, but will update this answer once I know more on this. I did however find this, which might be a step in the good direction :

> ... the question "is **P** a proper subset of **NP**?" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?".
> \- https://en.wikipedia.org/wiki/P\_versus\_NP\_problem#Logical\_characterizations

EDIT : **P = NP** cannot be written in propositional logic, but can be written in first order logic (as can be seen here : https://math.stackexchange.com/questions/51740/expressing-p-np-as-a-first-order-formula). The language of first order tautologies is **PSPACE-complete** when considering Boolean variables, and undecidable when considering natural variables. **P = NP** apparently considers natural variables.

# Answer
> 6 votes
It isn't meaningful to say that a single specific question is in NP or any other complexity class. In order to classify things as being in P, or NP, or co-NP, etc. they need to be sets of problems with some parameter. So for example, the problem "Is the positive integer n prime" is a question where we can discuss this sort of thing.

In a certain overly pedantic sense, the correct answer to your question is that the problem you care about is in P, since there's an algorithm which will answer every question of your form in polynomial (in fact constant time). But we don't know if that algorithm is just "Return TRUE" or is "Return False."

The idea that the video may be touching on is the idea that if P != NP, then in general, finding proofs is hard. In fact, "Is statement S provable in formal system A with a proof of length at most x" is an NP-hard problem" (Questions in this are things like "Is there a proof of Fermat's Last Theorem that's shorter than 5 pages.") . And we also expect that if P != NP, for most "natural" NP-complete problems, random instances will often not be easy. So if P != NP, then searching for proofs should often be difficult, and thus we shouldn't be surprised that the proof that P != NP would itself be one of those. This may be what they were trying to say.

# Answer
> 3 votes
There are *grave* conceptual issues at hand here.

Establishing proofs is the aim of mathematics. This is a task carried out by humans, usually using pen (or pencil) and paper. Some amount of coffee might be involved in the process too. This definitely has *nothing to do* with $\mathsf{NP}$.

Now, "proofs" may be meant in the sense of logic and proof systems. These are procedures with axioms and deduction rules applied to them which yield truthful statements (according to the underlying logic). This is the realm of Gödel's incompleteness theorems and has important connections to computability theory. This, also, has definitely *nothing to do* with $\mathsf{NP}$.

Then, there is another notion of "proof" in complexity theory, namely that of an interactive proof system (IPS). A prover, generally with unbounded computational capacity, tries to convince a verifier of a statement; the verifier is a limited machine, but which cannot be easily fooled. (Note how this has much more to do with a real-life argument than with a mathematical proof.) It has been shown that the class of decision problems that can be verified by such a system when the verifier is a probabilistic poly-time Turing machine (which is the usual setting) is equal to $\mathsf{PSPACE}$. This does seem to have a bit more to do with $\mathsf{NP}$.

However, $\mathsf{NP}$ does not contain proofs. $\mathsf{NP}$ (as well as any of the classes $\mathsf{coNP}$, $\mathsf{P}$, $\mathsf{PSPACE}$, and so on) contains *decision problems*. One of the *definitions* of $\mathsf{NP}$ is that it contains those problems for which one can efficiently (i.e., in poly-time) and determistically verify the solution of yes-instances. In a sense, this is equivalent to an IPS in which the verifier is deterministic and obtains a single message from the prover. You can easily see how this is quite of a restriction to the usual IPS setting.

Thus, if you could say something the likes of "$\mathsf{NP}$ is about proving things," then you could equally say "$\mathsf{PSPACE}$ is about proving things." I do not think this is a particular enlightening way of thinking about it.

---
Tags: complexity-theory, p-vs-np
---


title: Big-O Notation and Calculus?

text:
# Question
Title: Big-O Notation and Calculus?
I was wondering if there are any calculus relationships implicit in Big-O notation.

For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step, and also involves looking at each part of the input a constant number of times. The derivative of a linear expression is a constant expression, so there is some hint of a pattern. However, I haven't been able to figure out how to generalize these facts to other Big-O classes of algorithms.

Do derivatives/antiderivatives help in matching an algorithm's Big-O description with its behavior?

# Answer
> an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step

I don't think that's really true. It seems to me that all you're doing here is observing that a discrete linear function changes by a constant amount at each step and wondering if that's connected to the fact that the derivative of a continuous linear function is constant. That doesn't have much to do with what linear-time algorithms necessarily do.

Since algorithms are intrinsically discrete and calculus is intrinsically about continuous properties, I'm not aware of any real relationships between them. One might occasionally use calculus, e.g., to bound a sum by an integral or in tricks like $$ \begin{align\*} \sum\_{i=1}^k in^i &= \sum\_{i=1}^k (i+1)n^i - \sum\_{i=1}^k n^i\\ &= \sum\_{i=1}^k \frac{\mathrm{d}}{\mathrm{d}n}n^{i+1} - \sum\_{i=1}^k n^i\\ &= \frac{\mathrm{d}}{\mathrm{d}n}\sum\_{i=1}^k n^{i+1} - \sum\_{i=1}^k n^i\\,, \end{align\*}$$ but I doubt that's the sort of application you had in mind.
> 3 votes

# Answer
A clear explicit relationship is that Big Oh is defined via limits which of course are central to calculus.
> 1 votes

---
Tags: algorithms, algorithm-analysis, complexity-classes, program-optimization, big-o-notation
---


# Question
Title: How to prove an implication about an upper bound mentioned in the proof of master theorem?
How can we prove rigorously the proposition "Suppose the if in case 1 is true, the equation 4.23 is true"? For given constant b and j, the implication in green makes sense. If the upper bound of j was fixed, the equation 4.23 follows directly. However, when n increases, the upper bound of j also increases, though is slower. It is where I find difficult to prove there always exists a value m \> 0 such that for all n \>= m, equation 4.23 is true.

# Answer
The statement $f = O(h)$ just states that there exists a constant $C\>0$ such that $f(N) \leq Ch(N)$ for all $N$ (some variants have this hold only for large enough $N$, but in most cases there is no difference). In your case, $f(N) \leq CN^{\log\_b a-\epsilon}$ for all $N$. This holds for $N = n/b^j$ in particular, and implies that $$ g(n) \leq C \sum\_{j=0}^{\log\_b n-1} a^j (n/b\_j)^{\log\_b a-\epsilon}. $$

As for the two different definitions of big O: suppose that $f(N) \leq CN^{\log\_b a-\epsilon}$ holds only for $N \geq N\_0$, and let $M = \max(C,f(1),\ldots,f(N\_0))$. Then $f(N) \leq MN^{\log\_b a-\epsilon}$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: How to prove any polynomial of degree $k$ is in $\Theta(n^k)$?
I want to prove that any polynomial of degree $k$ is in $\Theta(n^k)$. The coefficient of $n^k$, $a\_{k}$, is positive.

I know I need $0 \leq c\_{1}n^k \leq a\_{k}n^k + ... + a\_{0} \leq c\_{2}n^k$ for all $n \geq n\_0$.

The upper limit is easy to prove by taking $c\_{2} = \sum\limits\_{i=0}^k |a\_i|$

I don't know how to prove the lower limit. Any hints?

# Answer
> 4 votes
I think I found a good way to prove $p(n) = \Omega(n^k)$:

We want to show that $0 \leq cn^k \leq p(n)\ \forall{n \geq n\_{0}}$

We know $\lim\_{n\to\infty} p(n)/n^k = a\_{k}$

This gives us some intuition to choose $c \leq a\_{k}$.

Let $c = a\_{k}/2$

Now choose $n\_{0}$ such that $cn^k = (a\_{k}/2)n^k \leq p(n)\ \forall{n \geq n\_{0}}$.

or rearranging, $(a\_{k}/2)n^k \geq -\sum\limits\_{i=0}^{k-1} a\_{i}n^i\ \forall{n \geq n\_{0}}$

or we can relax the inequality and pick $n\_{0}$ such that $(a\_{k}/2)n^k \geq \sum\limits\_{i=0}^{k-1} |a\_{i}|n^i\ \forall{n \geq n\_{0}}$

or $(a\_{k}/2)n^k \geq n^{k-1}\sum\limits\_{i=0}^{k-1} |a\_{i}|n^{i-(k-1)}\ \forall{n \geq n\_{0}}$

or we can relax the inequality and pick $n\_{0}$ such that $(a\_{k}/2)n \geq \sum\limits\_{i=0}^{k-1} |a\_{i}|\ \forall{n \geq n\_{0}}$ since $n^{i-(k-1)} \leq 1$

Hence pick $n\_{0} = 2/a\_{k}\sum\limits\_{i=0}^{k-1} |a\_{i}|$

We now have a $c$ and $n\_{0}$ such that $0 \leq cn^k \leq p(n)\ \forall{n \geq n\_{0}}$

Hence proved.

# Answer
> 2 votes
Let \begin{align\*} p(n) &=a\_kn^k + \dots + a\_0 \\ &= \tfrac12a\_k n^k + \tfrac12a\_k n^k + a\_{k-1}n^{k-1} + \dots +a\_{0}\\ &=\tfrac12a\_kn^k + \left(\tfrac{a\_k}{2k}n^k + a\_{k-1}n^{k-1}\right) + \left(\tfrac{a\_k}{2k}n^k + a\_{k-2}n^{k-2}\right) + \dotsc\\ &\qquad + \left(\tfrac{a\_k}{2k}n^k + a\_{0}\right)\\,. \end{align\*}

Since $a\_k\>0$, we have, for all large enough $n$, \begin{align\*} \tfrac{a\_k}{2k}n^k + a\_{k-1}n^{k-1} &\geq 0\\ \tfrac{a\_k}{2k}n^k + a\_{k-2}n^{k-2} &\geq 0\\ &\vdots\\ \tfrac{a\_k}{2k}n^k + a\_{0} &\geq 0\\,. \end{align\*}

Therefore, we have $p(n)\geq\tfrac12a\_{k}n^k$ for all large enough $n$ (i.e., we can take $c=a\_k/2$).

# Answer
> 1 votes
For the lower limit, use the fact that for $i \> 0$, $\lim\_{n\to\infty} n^{-i} = 0$. This means that for every $\epsilon \> 0$ and $i \> 0$ you can find $n\_0$ such that for $n \geq n\_0$, $n^{-i} \< \epsilon$. Try to use this to prove that for every $\epsilon \> 0$ there is $n\_0$ such that for $n \geq n\_0$, $$ \sum\_{i=0}^k a\_i n^i \geq (a\_k - \epsilon) n^k. $$

# Answer
> 0 votes
Assume $c\_k$ \> 0. Given the coefficients, show that there is an n \> 0 such that $c\_0·n^0$, $c\_1·n^1$, ..., $c\_{k-1}·n^{k-1}$ are all less than $(c\_k·n^k)/(2n)$ (for each index you find a closed form expression for the smallest n). Then the polynomial is between $0.5·c\_k·n^k$ and $1.5·c\_k·n^k$.

# Answer
> 0 votes
We know that if the limit $$\lim\_{n-\>\infty}\frac{f(n)}{g(n)}$$ exists and is strictly between zero and infinity, then $f(n)\in\Theta(g)$. In this case, we need to evaluate the limit $$\lim\_{n-\>\infty}\frac{a\_k n^k+a\_{k-1}n^{k-1}+\cdots+a\_1 n+a\_0}{n^k}.$$ But this limit can be split into the $k+1$ limits $$\lim\_{n-\>\infty}\frac{a\_i n^i}{n^k},$$ where $0\le i\le k$. Each limit evaluates to zero for all $i\ne k$ and when $i=k$ the limit evaluates to $a\_k\>0$, so the polynomial is in $\Theta(n^k)$.

---
Tags: asymptotics
---


# Question
Title: "Greater than AND smaller than" condition in integer linear program with a binary variable
I found this related question, but that's not quite it

Is it possible to model this with integer programming:

$$A = \begin{cases} 1 & \text{if } B \geq C \geq D \\ 0 & \text{otherwise}\end{cases}$$

where $A \in \\{0,1\\}$, $B, D \in \mathbb R$ and $C \in \mathbb N$. We have upper and lower bounds on $B$, $C$ and $D$.

# Answer
> 0 votes
Thanks MrHug, I should have thought of this myself after your first hint.

after using the solution from here twice with the resulting binaries $A\_1$ and $A\_2$ we can form another problem: $$A = \begin{cases} 1 & \text{if } A\_1+A\_2 \geq 2 \\ 0 & \text{otherwise}\end{cases}$$

This one can be solved with a little hint from there:

$$A\_1 + A\_2 \geq 2 - M * (1-A) \\ 2 - \epsilon \geq A\_1 + A\_2 - M * A$$

where $M$ is a big value and $\epsilon$ is a very small value (above 0, below 1).

It's a bit unfortunate that so many variables are needed as $A$, $A\_1$ and $A\_2$ are cubic in my case. But I'm glad about this solution.

---
Tags: linear-programming, integer-programming, constraint-satisfaction
---


title: Shift-resolve parsing - questions

text:
# Question
Title: Shift-resolve parsing - questions
I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been attempting to grasp the construction algorithm more intuitively. I believe I succeeded (this presentation was the source of the ah-ha moment), but a verification of correctness from someone either familiar with the technique or the terminology contained therein would be greatly appreciated.

I'm going to describe my take on the solution (if it's correct, I believe it could be of help to other people attempting to understand the technique) and ask additional questions afterwards. To ensure there's no misunderstanding, I'm going to use the following standard notation: $a, b, c, ... \in T$, $A, B, C, ... \in N$, $... X, Y, Z \in N \cup T$, $\alpha, \beta, \gamma, ... \in \\{N \cup T\\}^\*$ and, as in the paper, $A \xrightarrow{i} \omega$ to denote rule number $i$. However, I'll probably use different names for concepts than the original paper.

Also, throughout the description, the equivalence relation $\kappa\_0$ is used.

### Construction

There are two kinds of items inside the parsing automaton: simple LR(0) items of the form $A \xrightarrow{i} \alpha \bullet \beta$ which I call *shift items* and items of the form $A \xrightarrow{i} \alpha \bullet \beta, m, n$ which I call *resolve items*; these tell the parser to push $n$ symbols back the input stream and then reduce by rule number $m$ upon the first symbol of $\beta$.

The grammar is augmented with the rule $S' \xrightarrow{0} S \\$$ and the construction starts with the shift item $S' \xrightarrow{0} \bullet S \\$ $ in the initial state.

Now, to construct the automaton, decide between these alternatives for each item in a state $q$:

1. If the item is a shift item $A \xrightarrow{i} \alpha \bullet \beta$, there will be a transition $q \xrightarrow{X} q'$ in the automaton, where $X$ is the first symbol of $\beta$.
2. If the item is a finished shift item $A \xrightarrow{i} \omega \bullet$, add a resolve item $B \xrightarrow{j} \alpha A \bullet \beta, i, 0$ for each rule $B \xrightarrow{j} \alpha A \beta$.
3. If the item is a resolve item $A \xrightarrow{i} \alpha \bullet \beta, m, n$, let $X$ be the first symbol of $\beta$. If $X \in N$, add a shift item $X \xrightarrow{j} \bullet \omega$ for each rule $X \xrightarrow{j} \omega$. If other items than $A \xrightarrow{i} \alpha \bullet \beta, m, n$ have $X$ as their dot lookahead, add a transition $q \xrightarrow{X} q'$ to the automaton. Every resolve item $C \xrightarrow{i} \alpha \bullet X \beta, m, n$ in $q$ will result in a resolve item $C \xrightarrow{i} \alpha X \bullet \beta, m, n + 1$ in $q'$.
4. If the item is a resolve item $A \xrightarrow{i} \omega \bullet, m, n$ it won't contribute any lookahead information and can be discarded, but first add a resolve item $B \xrightarrow{j} \alpha A \bullet \beta, m, n$ for each rule $B \xrightarrow{j} \alpha A \beta$.

This is, of course, just a sketch; actually, a closure of the state must be calculated first and only then can we deal with transitions/shifts and resolutions.

Transforming the automaton into a shift-resolve parsing table is trivial afterwards; just, as a minor variation, the authors of the paper interpret a resolution $r\_{0,0}$ as the accept action. Given the resulting automaton, I found it handier to simply treat a shift of $\\$$ as the accept action.

### Questions

The first one is, obviously, whether the process described above is correct.

The second one is about the equivalence relations. I can only guess that the equivalence relation $\kappa$ is what's responsible for deciding which resolve items are brought in when a finished shift item has been seen. $\kappa\_0$ seems to result in lookahead strikingly similar to the $FOLLOW\_{LM}$ sets of LSLR parsers. The paper describes a "finer equivalence relation" on page 11; is there a way to interpret this relation in intuitive terms? Are there other relations known?

And the final one is about conflict resolution. The paper describes well what constitutes an inadequacy in a shift-resolve automaton; is there a way of resolving these inadequacies, similar to ways of resolving conflicts in a traditional LR parser? Could something like *yacc*-style conflict resolution via precedence and associativity be implemented in a ShRe parser generator?

Thanks if you read all this and any answers will be greatly appreciated :)

# Answer
> 0 votes
Check if this is discussed in the encyclopaedic D. Grune, C. J. H. Jacobs, "Parsing Techniques: a Practical Guide" (Spinger, 2008). If not, perhaps it is similar enough to a technique discussed.

---
Tags: algorithms, formal-grammars, context-free, parsing
---