title: P = NP clarification

text:
# Question
Title: P = NP clarification
Let's use Traveling Salesman as the example, unless you think there's a simpler, more understable example.

My understanding of P=NP question is that, given the optimal solution of a difficult problem, it's easy to check the answer, but very difficult to find the solution.

With the Traveling Salesman, given the shortest route, it's just as hard to determine it's the shortest route, because you have to calculate every route to ensure that solution is optimal.

That doesn't make sense. So what am I missing? I imagine lots of other people encounter a similar error in their understanding as they learn about this.

# Answer
> 47 votes
Your version of the TSP is actually NP-hard, exactly for the reasons you state. It is hard to check that it is the correct solution. The version of the TSP that is NP-complete is the decision version of the problem (quoting Wikipedia):

> The decision version of the TSP (where given a length L, the task is to decide whether the graph has a tour of at most L) belongs to the class of NP-complete problems.

In other words, instead of asking "What is the shortest possible route through the TSP graph?", we're asking "Is there a route through the TSP graph that fits within my budget?".

# Answer
> 15 votes
There is a lot of decent answers here but none clear up a couple fairly important misunderstandings you seem to have.

Both P and NP are classes of what are called "decision problems." These are problems whose answer is YES or NO. (More formally they are all questions of given a string and a language, is the string in the language but that isn't an important distinction). In this sense, you are slightly incorrect in your understanding when you say "given the optimal solution of a difficult problem, it's easy to check the answer, but very difficult to find the solution" because decision problems don't have "optimal solutions." Problems where solutions can be "evaluated" and you are looking for the "best" solution are optimization problems, of which The Travelling Salesman Problem is an example. You can always turn an optimization problem into a decision problem by considering the problem "Given an instance of this optimization problem and an integer k, does the problem have a solution whose objective value is better than k?".

Another thing is you might be slightly confused as to what NP means. P is the class of decision problems that can be solved in Polynomial Time (that you seem to understand). NP stands for "Non-deterministic Polynomial Time" and it is the class of problems that you can easily check if an instance of the problem should give a YES answer given some extra information. So looking at our TSP problem, if I have an instance of TSP, and a solution whose total cost is less than k, then I can easily check that the solution is really a solution and that its cost is less than k. So the decision problem associated with TSP is in NP. But not all problems in NP are "hard". Actually P is a subset of NP because if you can easily solve the decision problem, you can easily check if an instance gives you a YES answer by just solving it.

But there are some problems in NP we think are hard to solve. Oversimplifying a little, we call these NP-complete problems. (Note these still must be decision problems). We can say a problem A is at least as hard as problem B if, we assume we have a blackbox oracle that solves problem A and we can use it to efficiently solve problem B. Let's again consider the TSP example. Clearly, if you could solve the optimization problem (that is get the optimal solution) then you could solve the decision problem. So the optimization problem is at least as hard as its corresponding decision problem. If we showed that the decision problem version of TSP was NP-complete (which it is) then we would know that the optimization problem TSP is also as hard as NP-complete problems, but it itself is not actually NP-complete because it isn't a decision problem. We call such problems NP-hard.

# Answer
> 6 votes
$P$ and $NP$ are classes of decision problems. The result of an algorithm for a decision problem is either "YES" or "NO". Even for a problem in $P$, such an answer cannot lead to a quick verification.

An instance of the decision problem version of TSP is "Given a collection of cities and intercity distances, is there a tour with total length less than $k$?", where $k$ is a constant specified in the instance. The result is "YES" or "NO". In neither case does the answer lead to a quick verification of the correctness of the answer.

The promise that you ask about is this: Given a particular proposed tour, one can in polynomial time:

* Determine that the proposed tour actually is a tour -- visits all the cities and only traverses intercity routes that exist (sometimes "that have finite distances" when one encodes missing routes as having length $\infty$).
* If so, determine that the length of the route is shorter than the constant $k$ in the problem instance.

Neither an answer of "YES" or "NO" provides a proposed tour.

The value of the model of $NP$ that you are using is that it encodes *a way* to make a solver: for each possible tour (typically an exponentially large set to iterate over) check to see if it is a tour and if its length is $\< k$. If so, report "YES". If we exhaust the collection of possible tours without reporting "YES", report "NO".

Note that this model suggests that the the difficulty in fast solution is **not** that checking the conditions takes a lot of time. The difficulty in fast solution is that there are too many potential tours to search through. So, if we could find some really, really smart way to restrict our search to only a tiny subset the collection of potential tours, we would have a fast solution for an $NP$ problem.

Binary search in a sorted list is an example where one has a smart way to search through the list evaluating only logarithmically many (in the length of the list) comparisons rather than linearly many comparisons. From this point of view, the TSP problem is hard because we don't know a substantially faster way to search through the proposed tours of every possible TSP problem instance.

# Answer
> 1 votes
NP is all about decision problems - problems where the answer is "yes" or "no".

A problem is in NP if for every instance where the answer is "yes", there is a hint that let's you easily prove that the answer is "yes". It doesn't say anything about instances where the answer is "no". They can be hard to solve.

The classical Travelling Salesman problem is: Given a set of cities and their distances, is it possible to find a tour shorter than k? And quite obviously, if the answer is yes then such a tour exists, and we can use it as a hint to easily show the answer is yes. If the answer is no, then nobody has yet come up with any hint that would let you prove that.

You stated a problem that you also called "Travelling Salesman" problem, but it is actually different. You ask: Given a set of cities and their distances and a tour, is that tour the shortest tour? In this case, if the answer is "no" then there is a shorter tour, and we can use it as a hint to easily show the answer is "no". That's exactly the opposite of NP: Your alternative version of the Travelling Salesman problem is one where for every instance where the answer is "no", there is a hint that lets you easily prove the answer is "no". Because it is the exact opposite of NP, this class is called "co-NP".

There are many problems like that. For every problem in NP, you could ask the question: "Is the answer for this instance of the problem 'no'", and of course the answer is exactly the opposite of the original problem. You just made the mistake of thinking that every problem with the words "travelling" and "salesman" in it is the same problem.

# Answer
> 0 votes
I find it most easy to understand by using the **3-SAT NP-complete** problem:

There are $n$ boolean variables and you can decide for each of them either to be set the $true$ or $false$ value and you are given $k$ clauses. Each of the clauses contains 3 variables and the constraints to them, like $(true OR false OR true)$, so the clauese would be satisfied if the first variable was set to true OR the second variable to false OR the third variable to true. The $k$ klauses can contain all possible combinations of three of the $n$ variables and you have to decide what value every variable should be set to, so that all clauses are satisfied.

If you find a combination of values for all variables, so that every clause is satisfied, your combination can be vermied very easy by just going once throuegh every clause and test it, but it can be very hard to find a combination which satisfies every clause.

---
Tags: np-complete, p-vs-np
---


# Question
Title: Easy-to-describe example of uncomputable function
After teaching my philosophy of cognitive science undegraduates what a Turing machine is, I mentioned that there are functions that can't be computed using a Turing machine. A curious philosophy major asked for an example of such a function. Most of the students in the class are not CS students and need not be mathematically adept, so I am limited as to what I can say, except to those students who want to hear more outside of class.

The only example of a particular function that is uncomputable that I could come up with off the top of my head was the halting problem, but that would have required a substantial digression, and it would seem quite obscure to most of the students if I walked them through it. It would also not be sufficiently useful to explain to the class why there must be uncountably many functions that are not Turing-computable. (First step: teach the countable/uncountable distinction.)

Is there an example of an uncomputable function that's relatively easy to describe and understand--more so than the halting problem?

# Answer
> 3 votes
A classic example of an uncomputable function is *The Busy Beaver Problem*: For each N, consider all N-state Turing Machines over the alphabet { \[blank\], 1 }; over all of those machines which always halt when started on a blank tape, find one which leaves the maximum possible number of 1's on the tape once it has halted; then f(N) is that number of 1's.

# Answer
> 2 votes
The proof that Radò's function $\Sigma(n)$ (maximal number of 1 written by an $n$ state Turing machine starting on a tape of all 0s before halting) isn't computable is rather simple, once you have a few building blocks. First, by convention Turing machines start in state 1 and halt by moving to the (non-existent) state $n + 1$ (so you can build a machine that does $M\_1$ then $M\_2$, written $M\_1 \mid M\_2$, by just renumbering the states of $M\_2$ and copying it after $M\_1$). Represent number $N$ by $N$ ones starting at the current head's position. Build a machine $\mathtt{Twice}$ that starts with $N$ on the tape and stops at the start of $2 N$ (can build $\mathtt{Dup}$, that copies $N$ after itself separated by a 0 -- can be done by overwriting 1 with 0, move to the end and add a 1, go back to the second 0, replace by 1 and go for the next 1, repeat until you hit 0, then move back to the start --, compose it with $\mathtt{Add}$ that adds $M$ \+ $N$ separated by a single 0 by just squashing them together then moving to the beginning), a machine $\mathtt{Inc}$ that increments the number on the tape (very simple, move to the first 0, write a 1 there, move back to the first 1), will also need machines $\mathtt{Write}\_n$ which writes $n$ on the tape and stops at it's beginning (can be done in $n$ states, just write a 1 and move left $N$ times; we will run this at the start, so it doesn't matter if it messes up the tape). Now assume there is a machine $\Sigma$ that reads $n$ and writes out $\Sigma(n)$. Compose $\mathtt{Twice} \mid \Sigma \mid \mathtt{Inc}$, say the result has $N$ states. Then $\mathtt{Write}\_N \mid \mathtt{Twice} \mid \Sigma \mid \mathtt{Inc}$ has $2 N$ states, but writes $\Sigma(2 N) + 1$, contradiction.

---
Tags: turing-machines, computability
---


# Question
Title: Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?
I was reading the Sipser's book on the *Theory of Computation, 3rd edition* and came up with a question. "Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?" I believe that the answer is **NO**, however, the Theorem 5.30 states something different.

There are two problems concerned in this question. One is $A\_{TM} = \\{ \<M,w\>\ |\ M \text{ is a TM and accepts } w\\}$ and the other is $EQ\_{TM} = \\{ \<M\_1,M\_2\>\ |\ M\_1, M\_2 \text{ are a TMs and } L(M\_1) = L(M\_2)\\}$.

On Page 238, the Theorem 5.30 is stated as follows:

> **Theorem 5.30** $EQ\_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable.

The proof is by mapping reduction of $A\_{TM}$ to $\overline{EQ\_{TM}}$, and at the same time, reduction from $A\_{TM}$ to $EQ\_{TM}$. This way, it has shown:

1. $\overline{EQ\_{TM}}$ is Turing-undecidable.
2. $EQ\_{TM}$ is Turing-undecidable.

Note that this reduction does not show that either of $\overline{EQ\_{TM}}$ or $EQ\_{TM}$ are not Turing-recognizable, since $A\_{TM}$ is Turing-recognizable.

On the other hand, on Page 209, we have the following definition

> A language is **co-Turing-recognizable** if it is the complement of a Turing-recognizable language.

which is accompanied by Theorem 4.22:

> **Theorem 4.22** A language is decidable iff it is Turing-recognizable and co-Turing Recognizable.

Therefore, we can obtain the following Corollary: *If a language is not decidable, then either the language itself, its complement or both of them are not Turing-recognizable.*

Therefore, it is shown on Theorem 5.30 that $\overline{EQ\_{TM}}$ and $EQ\_{TM}$ are Turing-undecidable. This does not tell me anything more than the following proposition:

> Either $EQ\_{TM}$ or $\overline{EQ\_{TM}}$ or both are not Turing-recognizable.

However, the Theorem 5.30 states something stronger.

Am I missing something?

# Answer
> 3 votes
> ... a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?

This claim is false. In fact, at least one of them (or both are) is Turing-recognizable. Assume that both the set (problem) $A$ and its complement $\overline{A}$ are not decidable. Then if both $A$ and $\overline{A}$ were recognizable (recursively enumerable) then that would mean $A$ and hence $\overline{A}$ are decidable (Theorem 4.22), a contradiction.

> ... however, the Theorem 5.30 states something different.

This theorem states that $EQ\_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable. In other words, both $EQ\_{TM}$ and $\overline{EQ}\_{TM}$ are not Turing-recognizable (recursively enumerable). This does not contradict to the above-stated claim.

Also, pay attention that the theorem 5.30 reduces $A\_{TM}$ to $\overline{EQ}\_{TM}$ (not to $EQ\_{TM}$ as you claim in your post) meaning that $EQ\_{TM}$ cannot be Turing-recognizable (otherwise $\overline{A}\_{TM}$ would be Turing-recognizable and hence decidable).

You are right, *if a language is not decidable, then either the language itself, its complement or both of them are not Turing-recognizable*, and since the theorem 5.30 proves that $EQ\_{TM}$ is not decidable, it follows that either $EQ\_{TM}$ either, $\overline{EQ}\_{TM}$ or both of them are not Turing-recognizable. But this result is weaker and does not contradict to the theorem 5.30. In fact the latter (weaker) result is not necessary since the theorem already establishes the stronger result.

# Answer
> 0 votes
It is easy to see that if both $L$ and it's complement $\bar{L}$ are recognizable by Turing machine, they can be decided (copy the input to a new tape, then run the machines for $L$ and $\bar{L}$ in parallel, the first one to stop tells you what the answer is; by assumption at least one of them stops in finite time). So the possibilities are:

* $L$ and $\bar{L}$ are both decidable
* $L$ is recognizable but not decidable, then $\bar{L}$ is not recognizable.
* None of $L$ and $\bar{L}$ are recognizable.

Check out Rice's theorem, it's proof is quite approachable. And it supplies examples of the third case above. For instance, let $L = \\{M \colon \mathcal{L}(M) \text{ is regular}\\}$, so that $\bar{L} = \\{M \colon \mathcal{L}(M) \text{ is not regular}\\}$. But both properties are non-trivial, thus non-decidable.

---
Tags: computability, turing-machines, reductions, undecidability
---


# Question
Title: Is $L=\{\langle M \rangle|M$ makes more than 10 steps on some input$\}$ decidable?
I want to show that it satisfies Rice's theorem:

(i) $L$ is non-trivial, since $\langle M\rangle \notin L$ where $L(M)=\emptyset$, as $M$ halts/rejects any input string in the first step.

(ii) if $L(M\_1)=L(M\_2)$ where $M\_1$ and $M\_2$ are turing machines, then $M\_1$ makes more than 10 steps on some input iff $M\_2$ makes more than 10 steps on some input.

I'm not sure if the second condition is true, and if so, why?

I know that you can always create redundant states/transitions by moving the read-write head go back and forth without changing anything, thus increasing the number of steps on a given input but giving the same outcome. But I'm not sure if you can always "shorten" a turing machine.

# Answer
Your first statement is true. The second is not true. You can construct infinetly many TMs accepting the same language by introducing redundant states and transitions (as you already mentioned). "Minimizing" a TM has nothing to do with the second statement since two machines accepting the same language do not have to be identical and minimizing a TM gives you another machine while you compare M1 and M2.
> 2 votes

# Answer
The answer to your question is yes.

In 10 steps the Turing machine can consider *at most* 10 symbols, the set of strings of 10 symbols is finite. You can check each of them to see if the machine is still running after 10 steps in finite time.

Be careful, Rice's theorem talks about properties of the language accepted by $M$, not directly $M$'s behaviour.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Minimum total waiting time for arrivals/durations
I have come up with the following problem, and cannot seem to find an effective way of solving it:

> Consider $n$ clients arriving at a service point at time moments $\\{a\_i\\}\_{i=1}^n$ whose duration of service (by a single employee, let's say) is known to be $\\{d\_i\\}\_{i=1}^n$. Choose the turn of servicing them, such that the total sum of waiting times (i.e. if we consider $\\{s\_i\\}\_{i=1}^n$ the start-of-service time for each client, then the total waiting time would be $\sum\limits\_{i=1}^n\\{s\_i-a\_i\\}$) is minimized.

The only difference in this problem to the Interval Scheduling that has a greedy method of selecting the earliest finish time first, is that here **all** clients have to be serviced. (whereas in the Interval Scheduling, some intervals may not be selected)

Is there an efficient greedy algo for this problem? Or isn't there? Many obvious or less obvious approaches do not seem to work, example with this:

* Client 1: arrival at 1, duration of 9
* Client 2: arrival at 2, duration of 13
* Client 3: arrival at 15, duration of $\epsilon$

The above example hints at choosing the smallest $a\_i+d\_i$ first, but I seem to be unable to prove this on an exchange argument... Is perhaps the problem NP-Complete?

# Answer
Yes, this is NP-hard. Since neither the $a\_i$ nor the $d\_i$ depend on the solution, the problem is equivalent to the problem of minimizing the sum of the completion times of the requests, which is known in the scheduling literature as "$1|r\_i|\sum C\_i$" and is NP-hard. Reference:

J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Ann. of Discrete Math., 1:343-362, 1977.

Also, I disagree with the statement that "the only difference to Interval Scheduling is that here all clients have to be serviced". There is one more important difference: in Interval Scheduling, the algorithm can just accept or reject the clients, while in this problem, even after the algorithm accepts a client, it has to choose when to start it.
> 1 votes

---
Tags: optimization, np-complete, dynamic-programming, greedy-algorithms
---


# Question
Title: The language of TMs accepting some word starting with 101
I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language

$$ L = \\{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has 101 as a prefix} \\}. $$

I have made an attempt at showing decidability of $L$:

On input $\langle M, w\rangle$ (where $M$ is a TM and $w \in \sigma^\*$):

1. Simulate $M$ on $w$.
2. If $M$ rejects and halts, reject. If $M$ accepts and halts, accept.

However, I'm not sure about moving forward after this. I do not want a solution, but I want some ideas/techniques as to what else I can prove about $L$.

# Answer
First, it should be intuitive that L is not decidable. Decidable means that you can can tell in finite amount of time if a word (in this case, coding of turing machine) is in L. In m opinion, this should be one of the first things that should come in mind while solving these kinds of questions.

Note that there are infinitely many string that have $101$ as prefix (for example $101, 1011, 10111$, or in general, $101^i$ for $ i \geq 1$).

There are several problems with your solution. First, the input for a TM for $L$ is $\langle M\rangle$, and not $\langle M, w\rangle$. Second, what happens if $M$ doesn't halt on $w$? Your TM for $L$ also doesn't halt, and hence can't decide $L$.

You can show that $ L \in RE\setminus R $.

Show that $L \in RE $ by describing a TM $M'$ that recognizes $L$ (meaning, on input $\langle M\rangle$, if $ \langle M\rangle \in L$ then $M'$ accepts $\langle M\rangle$, otherwise $M'$ rejects or doesn't halt.

An easy way to show that $L\notin R$ is a reduction $f$ from the halting problem $HP$ to $L$, such that if $\langle M,w\rangle \in HP$ , then $f(\langle M,w\rangle) \in L$ (Hint: $f(\langle M,w\rangle)$ we accept any input if and only if $M$ stops on $w$).
> 4 votes

# Answer
Hint: It is undecidable whether a given Turing machine accepts the empty string, or any other fixed string for that matter. Given a Turing machine, we can come up with a different Turing machine that rejects immediately if the input is not (say) $101$, and otherwise simulates the original Turing machine. What does that imply?
> 3 votes

# Answer
According to $Rice's$ $theorem$,

$\qquad$ $L$ = { $\langle M \rangle$ | $L (M) ∈ P$ } is undecidable if $P$ is a non-trivial semantic property of $\qquad$$L(M)$.

$\qquad$ P is the set of all languages that satisfies a particular property

If the following two properties hold, it is proved as undecidable −

Property 1 (Semantic) − If $M\_1$ and $M\_2$ recognize the same language, then either $\qquad$$\qquad$$\langle M\_1 \rangle ,\langle M\_2\rangle \in L$ or $\langle M\_1 \rangle ,\langle M\_2\rangle \notin L$.

Property 2 (Non-trivial) − There exists $M\_1$ and $M\_2$ such that $\langle M\_1 \rangle \notin L$ and $\langle M\_2 \rangle \notin L$.

Now,

$\quad$ 1) For any two TMs, $M\_1$ and $M\_2$ with $L(M\_1) = L(M\_2)$ either both $M\_1$ and $M\_2$ both accept all strings starting with 101 or both don't accept.

$\quad$ 2) There exists TMs that accepts strings starting with 101 and not accepting strings that starts with 101.

Therefore, the property of the language of a TM to start with 101 is a semantic and non-trivial. Hence, according to Rice's theorem, the given language is undecidable.

$L$ is recognizable as TMs that accepts when given as input strings starting with 101 always accepts and halts. But complement of $L$ isn't recognizable as both $L$ and complement of $L$ being recognizable will mean that $L$ is decidable(why?).
> 0 votes

# Answer
By Rice's theorem, it is undecidable if $M$ accepts a language with a non-trivial property (there are languages that have the property and others that don't). "Includes a string starting 101" is a non-trivial property.
> 0 votes

---
Tags: complexity-theory, formal-languages, turing-machines, automata
---


# Question
Title: Is the language of TMs that halt on some string recognizable?
I would like to show that the following language is recognizable: $$L:= \\{ \langle M \rangle \mid M \text{ is a TM that halts on some string}\\}.$$

How do I go about showing that this language is recognizable? I know that all recognizable languages are reducible to $HALT\_\epsilon$, so I figure if I can show that this language reduces to $HALT\_\epsilon$, then I am all set. I am defining $HALT\_\epsilon$ as follows:

$$HALT\_\epsilon:= \\{ \langle M \rangle \mid M \text{ is a TM that halts on } \epsilon \\},$$

where $\epsilon$ is the empty string. We can reduce $HALT$ on $x$ to $HALT\_\epsilon$ by a reduction $F(\langle M, x\rangle) = \langle M' \rangle $, where $M'(y) = M(x)$. For this reduction, we just ignore the input string $y$, which we know will be $\epsilon$ and just run $M$ on $x$ instead. Here, $HALT$ is defined as

$$HALT:= \\{ \langle M,x \rangle \mid M \text{ is a TM that halts on } x \\}.$$

I tried leveraging a similar technique to show that $L$ is recognizable, but I could not come up with anything better than this (somewhat crazy) TM that has a $HALT\_\epsilon$ oracle:

$ D^{HALT\_\epsilon} =$ On input $\langle M \rangle:$

1. Construct $N = $ "On input $x:$
    1. Run $M$ in parallel on all inputs $y\in \Sigma^\*$.
    2. If $M$ halts on any $y$ then *accept*, otherwise *loop.*"
2. Query the oracle to determine whether $\langle N \rangle \in HALT\_\epsilon$.
3. If the oracle answers YES, *accept*; if NO, *reject*.

*Note: My notation for TM algorithms is based on "Theory of Computation" by Sipser.* Step 2 for the definition of $N$ is a bit redundant, but in this type of context, is it okay to say something like "If $M$ halts on any $y$, then halt?"

I think all I have shown here is that $L$ is decidable relative to $HALT\_\epsilon$. I don't know if this implies that $L$ is recognizable. Can a Turing reduction be used in this manner to show that a language is recognizable? I'm confused as to what it means for a language to be recognizable. The task seems obvious if we go back to the definition: If some TM $R$ accepts strings in $L$, then $R$ recognizes $L$. So what if $R=D^{HALT\_\epsilon}$, and in the body of $D^{HALT\_\epsilon}$ we use some crazy reduction like $N$?

In general, to show recognizability, can we just come up with a reduction like $N$ that may or may not halt? Is it a problem that $N$ will never halt if $\langle M \rangle \notin L$?

# Answer
You can construct a recognizer following the same principle used for the recognizer for HALT. The only extra bit is how you check "all" inputs without getting stuck in a non-terminating computation.

An important technique you can use here is called dovetailing (expressed with inputs from $\mathbb{N}$):

1. Simulate one step of $M$ on $1$.
2. Simulate two steps of $M$ on $1$ and $2$ each.
3. Simulate three steps on $1$, $2$ and $3$ each.

$\quad\vdots$

* Terminate and accept once any of the simulated computations terminates and accepts.

If there is a halting input of $M$, this dovetailed simulation certainly finds it after finite time. If there is none, it loops and is correct in doing so.

This is, in essence, your $N$ (with an explanation why it's actually a computable function). You don't need the rest of the reduction in order to show that $L$ is semi-decidable.
> 6 votes

# Answer
Use nondeterminism. Given $M$, guess a string $w \in \mathcal{L}(M)$, simulate $M$ on $w$ (use your trusty universal Turing machine as a subroutine) and accept if $M$ accepts $w$.
> 1 votes

---
Tags: computability, turing-machines
---


# Question
Title: Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable
I tried to prove by contradiction.

$L\_{1}$ is undecidable and $L\_{2}$ is finite language then $\overline{L\_{1}}\cap \overline{L\_{2}}$ is decidable. $$L\_{1} = \overline{HALT\_{TM}} = \big\\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ doesn't halt on input } w \big\\}$$ $$L\_{2}=\emptyset$$ then, $$\overline L\_{1}={HALT\_{TM}}=\big\\{ \langle M, w \rangle \mid M\text{ is TM and }M\text{ halts on input }w \big\\}$$ $$\overline L\_{2}=\Sigma^{\*}$$ The intersection, $\overline{L\_{1}}\cap \overline{L\_{2}}$ is $\overline L\_{1}={HALT\_{TM}}$ is decidable and this is the contradiction.

Is it true?

Thanks.

# Answer
Unfortunately your proof is not correct. The claim you want to prove or disprove is:

> The union of *any* undecidable language and *any* finite language is undecidable.

To do a proof by contradiction, you need to take the opposite:

> The union of *some* undecidable language and *some* finite language is decidable.

Note that the "any" (universal quantifier) turns into "some" (existential quantifier) when you apply the negation.

You showed that a contradiction follows from:

> The union of *any* undecidable language and *any* finite language is decidable.

But unfortunately, that only proves:

> The union of *some* undecidable language and *some* finite language is undecidable.

In other words, you can't just pick specific languages and show that their union is decidable: you need to show that your proof will work for *any* arbitrary $L\_1$ and $L\_2$ fitting the requirements.

I would suggest that you instead start with an arbitrary undecidable $L\_1$ and finite $L\_2$ and, from there, show that $L\_1 \cup L\_2$ is undecidable. Here's a hint to get you started: is $L\_1 \setminus L\_2$ decidable or not?
> 2 votes

# Answer
I start with $L\_{1} \cup L\_{2}$ is decidable.

Decidable languages are closed under difference. So, $(L\_{1} \cup L\_{2}) \setminus L\_{2}$ must be decidable.

$(L\_{1} \cup L\_{2}) \setminus L\_{2}= L\_{1}$ but $L\_{1}$ is undecidable.
> 0 votes

# Answer
By contradiction. Suppose that for all $L\_1$ undecidable and $L\_2$ finite $\overline{L\_1} \cap \overline{L\_2}$ is decidable. Pick $L\_1$ any undecidable language. The language $L\_2 = \varnothing$ is certainly finite, it's complement is $\overline{L\_2} = \Sigma^\*$, so that $\overline{L\_1} \cap \overline{L\_2} = \overline{L\_1}$, and that one isn't decidable if $L\_1$ isn't.
> 0 votes

---
Tags: turing-machines, undecidability, halting-problem
---


# Question
Title: Determining the classification of languages
> $L\_0 = \\{ \langle M, w, 0 \rangle \mid \text{$M$ halts on $w$}\\}$
> $L\_1 = \\{ \langle M, w, 1 \rangle \mid \text{$M$ does not halt on $w$}\\}$
>
> $L = L\_0 \cup L\_1$

I need to determine where in the hierarchy of languages (recursive, recursively enumerable, not recursively enumerable) $L$ and its complement $\overline L$ belong. I reasoned as follows

$L = \\{ \langle M, w, x\rangle \mid \text{$M$ halts on $w$ when $x=0$, $M$ doesn't halt on $w$ when $x = 1$, $x \in \\{0, 1\\}$}\\}$

$L$ is clearly not recursively enumerable as a Turing machine wouldn't be able accept in all cases. It can accept only in case the input refers to $L\_0$, but can't in case the input refers to $L\_1$.

$\overline L = \overline L\_0 \cap \overline L\_1 = \emptyset$
Thus $\overline L$ is recursive.

Is my reasoning ok? This is a question from a previous exam paper.

# Answer
Here are two hints

1. If $\bar L$ would be decidable (recursive), then so would be $L$, and you just argued that $L$ is not even recursively enumerable. Maybe you have a closer look on what $\bar L\_0 \cap \bar L\_1$ really is. For example $\bar L\_0 = \\{ \langle M, w, 0 \rangle \mid \text{$M$ does not halts on $w$}\\} \cup \\{ \langle M, w, x \rangle \mid x\not=0\\} $.
2. If you want to argue formally correct that a language is not recursively enumerable, or decidable, then try to use a reduction, for example the many one reduction. Reduce a a problem, whose status you know, to $L$ and you can say something about $L$.
> 5 votes

# Answer
You can recognize (but not decide) $L\_1$ (essentially checking it ends "0", if so simulating $M$ on $x$ by a universal Turing machine $U$, otherwise reject).

$L\_2$ is essentially the complement of the language of $U$, which is not recognizable.

$L$ is not recognizable. If it was, say by a Turing machine $R$, you could run $R$ in parallel over $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$. The one that accepts tells you if $M$ accepts $w$, which is impossible to do in general.
> 0 votes

---
Tags: formal-languages, turing-machines, undecidability, halting-problem
---


# Question
Title: Is this language Recursively Enumerable or Not RE?
$L = \\{\langle M, k\rangle : M\\;\text{is a Turing Machine and } |\\{w \in L(M) : w \in a^\*b^\*\\}| \geq k \\}$

My Interpretation of language is that $L$ is a language which contains Turing machine whose language contains string greater than equal to $k$ and also strings belong to $a^\* b ^\*$.

My Analysis : Using Rice's Theorem,

$T\_{yes} = L$ and $T\_{no} = a^\*b^\*$

By rice's first theorem we can say that this language is Undecidable and by using rice's second theorem we can say this it is not even recognizable because $T\_{yes} \subset T\_{no}$.

My intuitive approach : As we know language $L$ is a set of TM which accept a set of strings length greater than or equal to k and are a subset of $a^\* b^\*$ then for language $L$ to be Recursively Enumerable there must be yes cases for turing machines which are fulfilling the requirement and for no cases it might halt and reject or might stay in loop but the issue here is there might exist a string in $a^\*b^\*$ which might get accepted later and there are infinite such strings so turing machine can never give yes cases. Yes cases can only happen if TM checks all strings of a*b* and rejects which are not a part of language but this will not happen as there are infinite strings.

*This is not a proof but just my intuition*.

Hence by using Rice's theorem we got to know that $L$ is not even Recursively Enumerable but I've been told that my interpretation of language itself is wrong and $L$ is Recursively Enumerable.

# Answer
$L = \\{\text{\<M, k\>| M is a Turing Machine and } |w \in L(M) : w \in a^\*b^\*| \geq k \\}$

Now we want to find whether $L$ is $RE$ or not.

Yes, indeed your interpretation of language $L$ is wrong.

$L$ is a language of strings of form $\langle M, k \rangle$ where $M$ is turing machine which accepts atleast $k$ strings of form $a^\*b^\*$.

So, now it's easy to see that $L$ is indeed $RE$. For that we can run $M$ on all strings of form $a^\*b^\*$ by using dove tailing approach. If $\langle M, k \rangle \in L$ then eventually $M$ will accept $k$ strings of form $a^\*b^\*$. And at that point we will accept $\langle M, k \rangle$.

So as per your question answer is that $L$ is $RE$.
> 2 votes

# Answer
Use the power of nondeterminism: Guess $k$ strings of the form $a^\* b^\*$, check that $M$ accepts all of them. So your language is r.e.

The property "contains at least $k$ strings of the form $a^\* b^\*$" is certainly not trivial, so your language isn't decidable by Rice's theorem.
> 0 votes

---
Tags: computability, semi-decidability
---


# Question
Title: Search for numerical solutions of underdetermined systems of quadratic equations
I'm looking for an algorithm that can quickly generate an approximate real number solutions of an underdetermined quadratic system. My task is to explore its algebraic variety. I'm interested in a special cases of quadratic systems that arise from mechanics:

set of variables $X = \\{ x\_i, y\_i, z\_i | 1 \leqslant i \leqslant N\\}$ (3\*N variables for $N \in \mathbb{N}$),

a system consists of two kinds of equations:

1) $(x\_i-x\_j)^2+(y\_i-y\_j)^2+(z\_i-z\_j)^2 + p\_{ij} = 0$ for $i, j \in \[1,N\]$ and $p\_{ij} \in \mathbb{R}$.

2) a more general case of 1: $(x\_i-x\_k)(x\_j-x\_k)+(y\_i-y\_k)(y\_j-y\_k)+(z\_i-z\_k)(z\_j-z\_k) + a\_{ijk} = 0 $ for $i, j, k \in \[1,N\]$ and $a\_{ijk} \in \mathbb{R}$.

It's guaranteed that variety of solutions is stable under small changes of coefficients. Here is an example with six-dimensional variety of solutions:

```
(x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 - 1 = 0
(x3-x2)^2 + (y3-y2)^2 + (z3-z2)^2 - 1 = 0
(x3-x4)^2 + (y3-y4)^2 + (z3-z4)^2 - 1 = 0
(x1-x4)^2 + (y1-y4)^2 + (z1-z4)^2 - 1 = 0
(x2-x1)*(x4-x1) + (y2-y1)*(y4-y1) + (z2-z1)*(z4-z1) - 1/3 = 0
(x1-x2)*(x3-x2) + (y1-y2)*(y3-y2) + (z1-z2)*(z3-z2) - 1/3 = 0
(x2-x3)*(x4-x3) + (y2-y3)*(y4-y3) + (z2-z3)*(z4-z3) - 1/3 = 0
(x1-x4)*(x3-x4) + (y1-y4)*(y3-y4) + (z1-z4)*(z3-z4) - 1/3 = 0

```

First, the algorithm is allowed to process this underdetermined system for some time. After that, it should get as input a set of constraints, like $x\_1 = 0$ or $z\_N = 1$, that turn the system into determined and quickly generate real solutions of it. For instance, one can find 8 real solutions of the system above after constraining all of $\\{x\_4,y\_4,z\_4,y\_3,z\_3,z\_2\\}$ to zero. **I need the algorithm to be scalable** so it can be applied for N=25-30, however **high precision of solutions isn't required**, 3-4 orders will do.

I've come up with a few approaches:

1. I tried to calculate Gröbner bases for such systems in Magma:

```
    P< x1,y1,z1,... > := PolynomialRing(RationalField(),3*N);
    I := ideal<P | my equations >;
    Groebner(I);

```

It works for zero-dimensional ideals, but coefficients were big even for N=7. In cases with dimensions \>0, calculation took too long (with enough RAM) and I have been able to compute Gröbner bases only for small systems. So I tried compute approximate Gröbner bases by running OpenF4 algorithm with datatype of coefficients changed on double, but the error grew significantly on each step of the computation.

2. Also I consider a calculation of Gröbner basis in grevlex order with subsequent transformation to lexicographic using FGLM-like algorithm.
3. I found this article https://arxiv.org/abs/1703.07810 and this looks useful for my purpose. I'm not familiar with such methods, but probably this is exactly what I need.

Here are my questions:

Is there a way to calculate an approximate Gröbner bases in reasonable time using my idea or any other approach, maybe for other order with subsequent transformation to lexicographic?

Can this problem be solved without Gröbner bases using methods like №3 or any other?

Any comments on my ideas and new suggestions would be highly appreciated.

# Answer
This is a bit late for you, perhaps, but it might be worth looking at cylindrical algebraic decomposition. CAD takes a general statement in the real closed fields (i.e. an arbitrary boolean statement involving equalities and inequalities), and returns a finite set of "solutions", each of which is a "procedure" to find those solutions by assigning the unknown variables.

I haven't tried it on your example (because I don't have any software handy to do it!), but as an example, here is the CAD of $x^2 + y^2 = 1$:

* $-1 \< x \< 1\\,\wedge\\,y = \sqrt{1-x^2}$
* $-1 \< x \< 1\\,\wedge\\,y = -\sqrt{1-x^2}$
* $x = -1\\,\wedge\\,y = 0$
* $x = 1\\,\wedge\\,y = 0$

There are four "solutions" in this decomposition, and each one gives you a way to find it, by first determining an assignment to $x$, and using that to get an assignment to $y$.

This would work extremely well if you knew which variables were going to be constrained, because you could specify that they appear first in each "solution". In this case, if you added the constraint that $x = 0$, you would just go through each solution and find that $y=1$ and $y=-1$ are the only solutions, since the last two don't apply.
> 1 votes

# Answer
When you have only type-1 equations, this is the graph layout problem. There are a variety of algorithms for finding approximate solutions to that problem; you might try seeing which ones can be adapted to your setting.

In particular, gradient descent looks like a good approach. For any particular assignment to the variables, let $e\_i$ denote the error in the $i$th equation (e.g., the squared difference between the left-hand side and the right-hand side). Let $\Psi = e\_1 + \dots + e\_n$ be the sum of errors for all $n$ equations. Then you could try using gradient descent (or any other optimization method) to find an assignment to the variables that minimizes the objective function $\Psi$. Note that solutions might be sensitive to the initialization for the variables, so you might want to repeat many times with different random initializations. This might give you reasonable solutions.
> 0 votes

---
Tags: numerical-algorithms, polynomials
---


# Question
Title: Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string?
I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings.

Example:

Set 1:

```
Some good product
Another product
Some name
Blah

```

Set 2:

```
Very long some product name with words blah
Another very long product name
asd asd sad sad asdsa
Blah blah blah

```

Set 1 contains "good" names. Set 2 contains "dirty" names.

I want: **for every item from Set 2 (further: item2) find the longest item from Set 1 (further: item1) so that all words from item1 are contained in item2**.

For the given example the pairs will be the following:

```
Very long SOME product NAME with words blah => Some name
ANOTHER very long PRODUCT name              => Another product
asd asd sad sad asdsa                       => none
BLAH blah blah                              => blah

```

So far I couldn't think of anything better than brute force algorithm:

1. Split every string from Set 1 into words = we get a set of lists of words, let it be Set 3
2. Split every string from Set 2 into words = we get a set of lists of words, let it be Set 4
3. Pick up a list of words from Set 3 (further: list3), compare it to all the lists of words from Set 4 until find some list which is fully contained in the list3.

However it has pretty high complexity and works quite slow. My simple implementation takes about 1.8s to find 1 pair (Set 1 has 3mln items, Set 2 has 4mln items). If I implement same task using MySQL-fulltext indexes (it allows to search for strings which contain all given words) then 1 search takes about 0.4s. So I'm wondering whether there are some good approaches which could be applied here with small blood :)

My programming language is PHP7. The data is stored in MySQL DB.

# Answer
> 2 votes
I'll list two possible approaches that might be reasonably effective in practice, though their worst-case running time is no better than what you listed.

# Indices

You can build up an index for each word. Build a hash table. For each word that appears in any clean name, the hashtable maps that word to a list of all dirty names that contain that word. This hashtable can be built up once in a linear scan of the set of dirty names (Set2).

Then, given a clean name, iterate over the words in the clean name. For each word, look it up in the hash table, and iterate over all the dirty names that contain that word, and check how many words it has in common with the clean name. Keep the best match.

This can be optimized a bit. If the clean name contains a word that occurs in many dirty names, handling that word will be slow. So, you could find the number of times each word occurs in some dirty name (its frequency) and store this in a hash table. Then, given a clean name, you could iterate over the words in the clean name in order of increasing frequency, keeping track of the best match you've found so far. If you've found a match of length $\ell$, then you can stop the iteration early without iterating over $\ell-1$ highest-frequency words in the clean name without missing any valid matches.

# Tries

The order of words in a name is irrelevant, so sort the words in each phrase. For instance, 'some good product' becomes 'good product some'. Do this to each name in each set.

Next, build a trie to represent the set of good names (Set1). For instance, in your example the trie will be

```
+-- another --+-- product --+
|`-- blah --+
|`-- good --+-- product --+-- some --+
 `-- name --+-- some --+

```

Now, pick a dirty name. We want to find a match for it from the trie. I suggest you use a recursive algorithm to find all matches: to find a match for the name $w\_1 \cdots w\_n$ in the trie $T$, check whether there is an edge out of the root of $T$ labelled $w\_1$, and if so, recursively find all matches for $w\_2 \cdots w\_n$ in the subtrie pointed to by that edge; also recursively find all matches for $w\_2 \cdots w\_n$ in $T$. Once you have found all matches, keep the longest one.

For instance, for 'another very long product name', after sorting this becomes 'another long name product very'. You look that up in the trie by recursively finding all matches for 'long name product very' in the subtrie `+-- product --+`, and by finding all matches for 'long name product very' in the main trie.

This search process can be optimized in various ways, e.g., by keeping track of the longest match found so far and stopping early if there's no way the recursive call could find a longer match based on how many words you've matched so far and how many words remain.

There's no requirement to sort by lexicographic order. You can sort in any other order, as long as it is consistent. For example, you could sort by the frequency of words in the entire dataset (into the least common words first), which might help reduce the number of recursive calls.

---
Tags: strings, sets, substrings
---


# Question
Title: To calculate how many times a certain year repeats itself in the calendar within a given year range
Let's say I have a year $Y$. I wanna know how can I calculate the number of times the calendar configuration of the year $Y$ repeats itself in the year range $\[A, B\]$.

Is there any method to it without brute force, in a pretty efficient way?

NOTE: I'm talking about the Gregorian Calendar.

# Answer
> 1 votes
Basically, the "configuration" of a year, if I understand well can be described as a state $Y\_i = (D\_i, L\_i)$ with $D\_i$ the weekday of January the $1^{st}$ (0 to 6 for monday to sunday) and $L\_i$ which is 1 if $Y\_i$ is a leap year and 0 else.

So, comparing the state of 2 years, you can decide wether they have the same configuration.

As a year has 365 days (366 for a leap year) and $365 \mod 7 = 1$ (2 for a leap year), there is a simple relation:

$D\_{i+1} = D\_i+L\_i+1 \mod 7$

As there is one leap year every four years (without 100-exception), it is interesting to also notice there is a 5-step on weekday every 4 years:

$D\_{i+4} = D\_i+5 \mod 7$

Now, how to not loop on all year ?

Let's consider leap years are all years divisible by 4 without exception. Then, from a starting year $Y\_0$, we seek the next year with same configuration $Y\_s$. Let's consider all possibles values of $M\_0 = Y\_0 \mod 4$ :

* $M\_0 = 0$, then $Y\_0$ is a leap year, as $GCD(5, 7) = 1$, 7 of the 5 steps (28 years) are necessary to reach the same configuration: $Y\_s = Y\_0 + 28$ and $M\_s = 0$
* $M\_0 = 1$, then $Y\_s = Y\_0 + 6$ and $M\_s = 3$
* $M\_0 = 2$, then $Y\_s = Y\_0 + 11$ and $M\_s = 1$
* $M\_0 = 3$, then $Y\_s = Y\_0 + 11$ and $M\_s = 2$

Thus, if the considered year is a leap year, you have exactly the same configuration every 28 years, else, you have 3 times the same configuration every 28 years. In the latter case, the $B-A \mod 28$ reamaining years may be simply considered with above rule.

To consider the 100-exception, you may do the same work adding an extra variable modulo 100 (quite more laborious).

# Answer
> 1 votes
Optidad’s answer is almost perfect, but only if you ignore week numbers.

If the first four days of a year or more fall into the same week, then they are in the first calendar week of the year. But if only one, two, or three of the first days fall into the same week, then they are in the last calendar week of the previous year.

The last calendar week of the previous year is usually the 52nd week. There is an exception if the previous year was a leap year, and it had the first four days in the first calendar week, and the last four says in the last (53rd) calendar week.

So you have fifteen, not fourteen different configurations. If exactly the first three days are in the same calendar week, then you have a different configuration if the previous year was a leap year.

One more complication: The rules what is a “calendar week” and what is the first day of a week are different from country to country. In some countries the week is from Sunday to Saturday, in others it is Monday to Sunday. In the first case the exception is a year starting on Thursday after a leap year, in the second case it is a year starting on Friday. Lucky enough we don’t have consecutive leap years.

---
Tags: efficiency, counting
---


# Question
Title: How to show that a $\log_2(x)$ is a recursive function?
I have a problem for the comprehension of how to prove that a function $ \log\_2 : \mathbb{N} \rightarrow \mathbb{N}$ defined as: $$\log\_2 (x)= \begin{cases} y & \text{if $x=2^y$} \newline \bot & \text{otherwise} \end{cases}$$ is recursive. I think that I need to use minimization operator but I don't know how to do that.

# Answer
> 4 votes
Once you have proved that $|x-2^y|=0$ is a decidable predicate, the function $$\log\_2(x) \equiv \mu y(|x-2^y| = 0)$$ should match the description of the function given and proves that it is recursive.

Edit: To show that $|x-2^y|=0$ is decidable, show that $\overline{\text{sg}}(|x-2^y|)$ is recursive, which requires you to show that $|x-z|$, $2^y$, and $1 - \text{sg}(z)$ are recursive, then use substitution.

$|x-z|$ can be defined as $(x-z) + (z-x)$ where cut-off substraction is used in the latter and you can use $x^y$ is a primitive recursive function to show that $2^y$ is recursive. $\text{sg}(z)$ is computable by noting that $\text{sg}(0)=0$ and $\text{sg}(z+1) = 1$.

---
Tags: computability, recursion, primitive-recursion
---


# Question
Title: Given the Equivalence relation R = { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes 1 and 2?
Given the Equivalence relation R = { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes of 1 and 2?

I can't really see the equivalence classes of infinite sets. Only by having a drawing of all elements can I distinguish the answers, wich is not the case in the above mentioned example.

What would be the best way to tackle such problems?

Thanks!

# Answer
There is no general way to answer such a question other than to repeat the definition. So one might answer for example for $1$:

> The equivalence class that $1$ belongs to is the set of all integers $n$ such that $1 + n \equiv 0 \mod 2$.

You might simplify this by noting that $1 + n \equiv 0$ implies $n \equiv 2-1$ or $n \equiv 1$ modulo $2$, giving:

> The equivalence class that $1$ belongs to is the set of all integers $n$ such that $n \equiv 1 \mod 2$.

---

Now the answer that the asker is looking for will probably be "the odd integers". If they disagree that the above answer is correct I would argue that the question is too vague however, as in my view the above is perfectly correct.
> 0 votes

---
Tags: sets
---


# Question
Title: What is the most effective way to learn, understand, and utilize an algorithm?
In order to keep my interviewing skills sharp, I solve one algorithm/data-structure problem every day, from sites like Leetcode or HackerRank.

If I am not able to solve it after 45 minutes or so, I usually refer to the solution. I review it, understand it, and move on.

However, I have found that I do not really learn anything at all by looking at the solution. Even though I understand the solution at that point in time, it doesn't really stick with me. I am not able to learn the approach and trick of that solution, for purposes of retaining and utilizing it later. And, if I ran into a similar question in the future, I would not remember how to utilize the approach that I have definitely seen before.

What is your technique or suggestion in learning such approaches/techniques in solving algorithm/data-structure problems?

If this question is not in the right `Stack Exchange` please let me know.

# Answer
> 1 votes
To be an algorithm designer, you have to do some steps.

**First**, learn the basics of algorithmic thinking. You can learn it by using a simple programming language book. Choosing the language is not important. You can take a look at this page for finding a book. After finishing this step, you have to be able to present pseudocode (or code written in a specific language) for simple problems, for example:

* Searching in a list: there is a list of numbers, and we want to see a specific number is in the list or not.
* Sorting a list
* Finding the greatest common divisor of two numbers

**Second**, learn the important data structures— link-list, stack, queue, and tree— and their algorithms. For doing this step, you can read the books of data structure written for bachelor students of computer science. For example, Fundamentals of Data Structures by Ellis Horowitz and Sartaj Sahni is a good book. At the end of this step, you have to know/do the following things:

* What is a data structure? How we can iterate over the elements of a data structure? How we can add a new item(/remove an item) from the data structure?
* What are the main features of each data structure?

**Third**, learn conventional algorithm design techniques— divide and conquer, dynamic programming, greedy, back-track, branch and bound. For doing this step, you can read the algorithm design books written for bachelor students of computer science. For example:

* Foundations Of Algorithms, Richard Neapolitan
* Introduction to Algorithms, Thomas H. Cormen, et al. (Chapters 1-17) After doing this step, you can solve a large range of algorithmic problems, like the problems that can be found on this website: onlinejudge.org.

**Forth**, learn specialized algorithm design techniques, like randomized algorithmic techniques, parallel algorithmic techniques, distributed algorithmic techniques, approximation algorithmic techniques, etc. For each case, there are some books written for graduate students of computer science.

Besides, there are some other steps, like learning the basics of the theory of computing, complexity classes (NP-complete and P-complete theories), and a lot of other things. It depends on your goal and the level that you want to be reached.

---
Tags: algorithms, data-structures
---


# Question
Title: Selection over combinatorics that satisfies a distribution
I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not.

Here is the problem :

**Consider a list of M sets that ( M = 10000 )**

* ***each set contains integers in range 1... N. (Let's say N=50)***
* ***each set has the size of K. ( Let's say K=10)***
* ***each element in the set is distinct.***

Sample sets are

1. { 1,2,3,4,5,6,7,8,9,10}
2. { 2,4,5,7,9,11,13,15,20,25}
3. { 4,5,8,12,16,30,41,42,45,49}
4. { 2,6,11,18,24,27,31,36,39,43}

....

10000. { 3,5,8,17,19,23,34,37,38,46 }

**You should select L sets(Let's say L=1000) from given 10000 sets. This selection must approximately satisfy a distribution table like below**

* 1=\> 100 %
* 2=\> 80 %
* 3=\> 100 %
* 4=\> 15 %

...

* 50=\> 20%

**It means that 1 should occur in all selections, 2 should occur 80% of the selections and goes on ... I will try to solve the problem by trying a random-walk algorithm that exchanges a set in each iteration.**

I'm sorry if I did not express my problem well. It would be great if you could share similar problems with mine or could express your approach to the problem.

# Answer
> 3 votes
Consider the following special case where for each element $i$ the table contains the constraint $\\#i \geq (1/l) \cdot l$. This means we need to select the sets in such a way that each element appears at least once. This problem is called the set covering problem, where you have to output whether there is a subset of $l$ sets in the input that covers all the elements in the ground-set. It is an NP-complete problem and since it is a special case of your problem, your problem is NP-complete as well (it is clearly in NP since an NTM can guess all possible tuples of $l$ subsets and accept if the union of subsets in any of the guessed tuples covers the ground-set). So You should not expect a polynomial answer.

On the other hand, an exponential trivial solution would be to try packing all sets of $l$ subsets which are at most $n \choose l$ and try for each of them if they satisfy all the constraints in $O(l \cdot r)$ where $r$ is the number of the constraints. This totals in an $O(n^{l+1}r)$. There are a lot of improvements on this running time I think but you should not expect something sub-exponential.

---
Tags: algorithms, combinatorics, constraint-satisfaction, set-cover, selection-problem
---


# Question
Title: Will a Greedy algorithm give a correct result for minimum partition?
Will a greedy method of picking the item that causes the largest difference each time lead to the optimal result in the minimum partition problem?

Let's say I have a set $\\{a\_1,a\_2,a\_3,...a\_n\\}$, now I have to divide it into two subsets so that the difference between the sums of the two subsets is the minimum possible.

**Greedy Method:**

I have the given set of numbers and an empty set. On each iteration, I select the number from the first set and check which causes the minimum difference and put that into the second set and repeat the process again.

For example: let us say I have to partition $\\{1,2,3,4\\}$ into two subsets so that their respective sums are minimum.

So using the above method I would do the following steps:

Select the number that causes the min diff so far ie.

$\\{2,3,4\\}$ and $\\{1\\}$ diff = $9$

$\\{1,3,4\\}$ and $\\{2\\}$ diff = $6$

$\\{1,2,4\\}$ and $\\{3\\}$ diff = $4$

$\\{1,2,3\\}$ and $\\{4\\}$ diff = $2$

so the minimum is $\\{1,2,3\\}$ and $\\{4\\}$

I use the above configuration and repeat the same process, and I land up with the partition $\\{2,3\\}$ and $\\{4,1\\}$ which has a difference of $0$ and is the correct answer.

**So, assuming the numbers given are all positive integers, will the greedy method work for all inputs or will it fail for some.** **Is dynamic programming the only way to get the optimal solution?**

# Answer
> 2 votes
This does not always lead to the optimal solution. For example for input $\\{1,11,16,19,20,30,36,40,41\\}$ it gives $\\{1,11,16,19,20,36\\}$ and $\\{30,40,41\\}$ with a difference of 8, while a difference of 0 is possible: $\\{1,40,36,30\\}$ and $\\{41,20,16,11,19\\}$

# Answer
> 1 votes
As Jeff Erickson says in his book, "greedy algorithms never work". (Except in the --rare-- cases where they do, and they offer simple, efficient approximations to many NP-hard search problems, see for instance Kun's "When Greedy Algorithms are Good Enough: Submodularity and the (1 – 1/e)-Approximation", check also Krause and Golovin's survey for more in-depth discussion.

---
Tags: algorithms, greedy-algorithms, partitions
---


# Question
Title: How to prove greedy algorithm for number partitioning?
> the partition problem (or number partitioning) is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2.

There is a greedy algorithm for this problem:

> One approach to the problem, imitating the way children choose teams for a game, is the greedy algorithm, which iterates through the numbers in descending order, assigning each of them to whichever subset has the smaller sum. This approach has a running time of O(n log n). This heuristic works well in practice when the numbers in the set are of about the same size as its cardinality or less, but it is not guaranteed to produce the best possible partition. For example, given the set S = {4, 5, 6, 7, 8} as input, this greedy algorithm would partition S into subsets {4, 5, 8} and {6, 7}; however, S has an exactly balanced partition into subsets {7, 8} and {4, 5, 6}.

But, I don't know how to prove "This heuristic works well in practice when the numbers in the set are of about the same size as its cardinality or less". Can anyone help?

# Answer
> 3 votes
There is nothing to prove about the statement you highlight. It is an *empirical* statement.

In order to have something to prove, you will need to formulate this claim formally in some way or another. There are many options, including average-case analysis, smoothed analysis, and restricted instances (which is what the statement points at). Until you have done so, it is impossible to prove or refute the statement.

The example given in your source shows that, in fact, the heuristic doesn't always succeed. Perhaps it gives a good approximation in some circumstances. The statement, unfortunately, doesn't hint at a provable claim which has any chance of being true.

# Answer
> 0 votes
What you describe is just an approximate algorithm for the Job Shop problem (which is also NP-complete, reduced from Partition -- split a set of integers in two so that both add to the same value, the problem you describe) that can be shown has an approximation ratio of 2. See for example this set of slides for a proof and hints at refinements that get better approximation ratio.

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: Greedy heuristic for buying fewest fridges of set temperature for products that can be kept in some temp. ranges?
> We have a set of $n$ products, each $i$th product can be kept in a temperature between $c\_i$ and $h\_i$.
>
> We have to buy fewest number of fridges for these products. The fridges can only have a fixed temperature.

For me I think of this problem as intervals of product temperatures that are placed on the axis.

My idea to solve it is to see which product's temperature range overlaps with most other products temperature ranges, then we can place these products in one fridge.

But the algorithm for this would be inefficient..

What's a simple greedy solution for this? any ideas?

# Answer
The formalized problem here is selecting the minimum number of points such that for each temperature interval $\ell\_i\in L$ we have at least one point that covers it. Let each interval $\ell\_i$ be represented by $(c\_i, h\_i)$

1. Order all $\ell\_i\in L$ by their $h\_i$.
2. While there are still items that need fridges.
    1. Buy a fridge and set it to $h\_1$.
    2. For every item with $c\_i\leq h\_1$, put item $i$ in the fridge and discard the interval from $L$

The runs in $O(n\lg n)$ time.

We can show this is optimal. Let the solution obtained above be $S$ and let any feasible solution be $R$. We can show that for any point $x\_i\in R$, there is at most one point from $S$ between $x\_{i-1}$ and $x\_i$.

If the above is not true then we have some $x\_{i-1}\leq y\_{j-1} \< y\_j \< x\_i$ for both $x\in R$ and both $y\in S$. In this case, the interval $\ell\_k$ ending at $y\_j$ would not be covered by $R$. $x\_i$ can’t cover it, since by definition $y\_j \< x\_i$. $x\_{i-1}$ can’t cover it either. If it did, that would mean the start point of $\ell\_k$ would be less than $x\_{i-1}$ and thus also less than $y\_{j-1}$. This can’t be the case, though, because then $y\_{j-1}$ would have covered $\ell\_k$, therefore removing it from the list of intervals in the next step our algorithm. Thus we have shown that for any point $x\_i\in R$, there is at most one point from $S$ between $x\_{i-1}$ and $x\_i$ and therefore $S$ is optimal.
> 4 votes

# Answer
I'd start with the shortest temperature range, stash everything that fits in it into a refrigerator, rinse and repeat. But a temperature range may overlap several that don't overlap among themselves, among those that do overlap search for a temperature that hits most ranges. This heuristic sounds like it should give a good solution, but I'd first look if there are is some counterexample (and I'd be thrilled to see a proof that it gives an optimum...).
> 0 votes

---
Tags: greedy-algorithms
---


# Question
Title: How are Operating systems involved in execution of programs?
By my understanding, operating system is the abstraction layer above hardware. Which means that an operating system that supports two different CPU architectures can run the same code. But I still cant understand the details/steps of executing a given program.

Suppose, I have a program that takes 2 numbers from the user, adds them and displays the answer. There are few steps in which the program does its work (Might be missing something or wrong somewhere, feel free to correct):

1) Double clicking the program file icon.

(a) How do the GUI and the mouse (and RAM) interact to identify which icon is clicked?

2) Loading of program in the Main memory using the address of the icon clicked.

(b) How is the os involved in finding that file from the disk?

3) Input of 2 numbers (CPU reads instructions of taking input from keyboard).

(c) Will the example of 2 different keyboards (For eg: one with 'fn' key like in laptops and one of full size) be a good example for explaining the need of device controllers and drivers?

4) Adding of the 2 numbers (Arithmetic operations).

(d) Is the os responsible for providing the CPU with the addresses of the operands and operators?

5) Displaying the output on the monitor.

I understand that the question might be broad, but I am not able to piece together all these things just by reading books (like 'Operating System Concepts by Galvin').

Also, I like as much detail as possible as it makes things more clear.

# Answer
> 1 votes
At one level you have hardware: A computer with a CPU, RAM, hard drive, graphics card, monitor, keyboard and so on.

Then on the lowest level of the operating system you have code that can talk to these devices. That code allows the operating system to read or write data from the hard drive, determine the location of the mouse, and so on.

At a higher level of the operating system, the OS has code to assign address space to processes, start processes and kill them, allow these processes indirect access to the hardware.

Above that, it is just code. You have a mouse reporting it's location, you have graphics hardware that can display a cursor, so someone wrote code that keeps track of the mouse location and displays the cursor at the point corresponding to the mouse location. And then someone wrote code to display icons. And more and more and more code on top of that. And that's all, really.

# Answer
> 0 votes
Everything I will say does not represent the real thing but gives a taste of what is happening.

A computer is manufactured in a way with a pre installed “program” which is responsible of transferring electrical current to all the parts, cpu, hard drive, gpu, etc. This is binary logic.

Each one of the components, cpu, gpu, hard drive, mouse, keyboard has a really long documentation of how is it working. For example the mouse input is the “speed of lazer signal” and the output is just a string of 0 and 1s. Of course there are plenty of protocols for such kind of communications and this is what drivers are used for.

Now, the operating system comes and solves all these long documentations and interactions between the different components of your computer.

You can think of an OS as a huge monolithic while loop.
while True:
check the mouse if user clicked or moved
check the keyboard for keystrokes
check the network card if it receives messages
check the GUI if it needs to be refreshed
check for any interruption
...
etc

Of course many events are not handled on software level but there is special hardware for this case. For example the hardware CPU may have certain interruptions when devision by zero is encountered.

The main job of an OS is to enorchestrate all the communication between the components, but the story does not end here. A main job of the OS is also to forbid the user of accessing several locations of the hardware which may cause dis function. Also, it gives the power of parallelization of your applications. Imagine having to wait finishing a youtube video before printing a document on your printer.

---
Tags: operating-systems
---


# Question
Title: Combining merge sort with insertion sort - Time complexity
I am learning algorithms from the CLRS book on my own, without any help. It has an exercise which combines merge sort {O(n log n)} with insertion sort {O($ n^{2} $)}. It says that when the sub-arrays in the merge-sorting reach a certain size "k", then it is better to use insertion sort for those sub-arrays instead of merge sort. The reason given is that the constant factors in insertion sort make it fast for small n. **Can someone please explain this ?**

It asks us to show that (n/k) sublists, each of length k, can be sorted by insertion sort in O(nk) worst-case time. I found from somewhere that the solution for this is O($ nk^{2}/n $) = O(nk). **How do we get this part O($ nk^{2}/n $) ?**

Thanks !

# Answer
For your first question:
O(n logn) might be 4nlogn or 13nlogn or 0.1nlogn etc.

If you compare 4n^2 and 100nlogn you will see that for n \< about 200 the O(n^2) is faster. Big O is an asymptotic measure. It says what happens when n approaches infinity, but does not say anything about “smaller” inputs.

For your second question:
You have n/k sublists. Each sublist has length k and needs k^2 to be sorted with insertion sort. So multiply and you get n/k * k^2 = nk worst case. This is a way of parametrizing your algorithm’s complexity. If you choose k to be a constant c ex. k = 3 then you have n/3 sublists of length 3. Each one needs 3^2 = 9 execution steps and the overall amount of work is n/3 * 9 = 3n. You can also choose k to be a function of n, ex. k = f(n) = n/5. Then you have n/(n/5) = 5 sublists of length n/5. Each sublist needs (n/5)^2 = n^2/25 execution steps and the overall amount of work is 5 * n^2 /25 = n^2 / 5. Again, don’t assume that the one is faster than the other. n^2 / 5 and 3n describe “the same thing” written differently.

Finally, keep in mind that big O describes neither time nor space. It describes amount of work it needs to be done. If you take account the parallelization then for example assuming an ideal choice of pivots, parallel quicksort sorts an array of size n in O(n log n) work in O(log² n) time using O(n) additional space.

Some algorithms can be parallelized and some others can’t. Insertion sort for example is CPU favorable when the input size is comparable to the “block size” of the CPU. Divide and conquer algorithms are not fast for small inputs because the cpu must populate the code recursively. This means lot of memory to be allocated, lot of stacks, etc

The approach you are describing is a hybrid algorithm.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Identify the function call statement in the following snippet
I know that the main(sys.argv\[1:\]) is the function call statement but I have no idea about the other two variables and why it's used. Can anyone explain?

# Answer
> 2 votes
Are you writing an interview test right now ?

`__name__` is not a function. Is a special keyword used by Python and its value is `‘__main__’` if the script is run directly from terminal.
So if another script.py imports the one in the photo, the code inside the if statement won’t execute.

```
sys.argv

```

Is a list of the arguments of the script, if given any from the terminal. The reason of sys.argv\[1:\] is to exclude the first argument which is the file name of the script.

So you are right. The only function call statement is the `main(...)`

As far as for why the notorious

```
if __name__ == ‘__main__:’

```

is used, I would say for testing purposes. Imagine having a lot of .py files which import other .py files. You need to test each one separately from the other.

---
Tags: python
---


# Question
Title: Given a set of points in the plane all laying on the axis, find the number of right angled triangles
My approach:- I separated the x coordinates and y coordinates in 2 separate arrays..then i used the idea of pythagoras theorem by selecting three vertices(1 from x axis and 2 from yaxis and vice versa) but it's taking too much time..can anybody suggest me a better approach?

# Answer
> 1 votes
Here is a simpler solution if points lay only on the axis running in time $O(n^2)$. scroll down for a solution for the general case for any set of points in the plane.

Let us distinguish three case of triangles. the first is when the origin is a point of the triangle (and hence it must be the right angle). The second case is where two points lay on the $x$ axis and the right angle is at the $y$ axis. The third is analogous where two vertices lay on the $y$ axis and the right angle is at a point on the $x$ axis. Let us solve the first two cases the third one can directly be derived from the second one.

**The first case.** Note that by excluding the origin from the set any point on the $x$ axis with a point on the $y$ axis form such a triangle with the origin so the number of such triangles is number of points on the $x$ axis times the number of points on the $y$ axis (excluding the origin).

**The second case.** Lets $X$ be the list of all points on the $x$-axis sorted in ascending $x$ coordinate and analogously we define the list $Y$ for points on the $y$-axis. $X$ and $Y$ can be build in time $O(n \log n)$. Note that for a fixed point on the $x$ axis the other point must be on the other side of the $y$-axis and as further it is from the axis, as further the $y$-vertex must be from the origin. So we can again use a sliding window approach. For each point $x\_1$ to the left of the $y$-axix (we do the same later with the opposite side), iterate over all points $x\_2$ to the right of the $y$-axis one by one from the left to the right and for each find the coordinate $y$ such that the points $x\_1, x\_2 (0, y)$ are a right-triangle wirth right angle at $y$. This can be found easily, since $y$ must be the point of intersection of the circle having $\overline{x\_1 x\_2}$ as a diameter with the $y$-axis. Note that $x\_1, x\_2 (0,-y)$ is also such a triangle. So we will keep two iterators starting at $y$ and one going upwards the other downwards, for each $x\_2$ move both iterators till they reach a point whose absolute $y$-coordinate is not less than $y$. If it is equal to $y$ increase the number of triangles by one and iterate.

---

Here is an $O(n^2\log n)$ solution. For each point $p$ we will find the number of triangles that have a right angle at $p$ in time $O(n\log n)$. By iterating over all $p$ we can find the total count in the given time bound.

To this end let us sort all the points in polar angle relative to $p$ (we exclude $p$ from the set. Note that for a chosen candidate $p'$ we get that all triangles having an edge $\overline{pp'}$ have the third vertex at a fixed angle and hence all possible candidates appear consequently in the sorted list. So let us union all points having the same polar angle with $p$ in groups and keep a count for the size of each group. Now we can use a sliding-window approach to find for each group $g$ the group of points $g'$ (if it exists) such that $p$ forms a right triangle with each point of $g$ and point of $g'$. Note that by iterating over all groups we would have counted each triangle twice so we have to divide by 2 (or stop when the second pointer reach the first group).

---
Tags: algorithms, computational-geometry, mathematical-programming
---


# Question
Title: Prove using pumping free lemma for context-free languages
One of the exercises I tried to make I failed miserably.

The question was as follows:

Show that the language $L = \\{ w \\,|\\, n\_a(w) \cdot n\_b(w) = n\_c(w) \\}$ is not context-free. (with $n\_a(w)$ being the number of a's in the word, same for b's and c's)

For answers I first looked at common words not accepted by context free languages like $a^pb^pc^p$ with $p$ being the pumping length.

However I could not make a proof. Finally I got tired and with made the following construction. I assumed the length dynamic part of the ab's substring would only be one. (then it doesn't matter that much whether it is an 'a' or 'b', I chose the latter). And constructed my word like this:

$\theta b c^{n\_a(\theta)} c^{n\_a(\theta)\cdot n\_b(\theta)}$, with $\theta$ being some random string in $\\{a,b\\}^\*$with 'b' being the dynamic substring v and $c^{n\_a(\theta)}$ being the dynamic substring y.

With this construction $uv^0xy^0z = \theta c^{n\_a(\theta)\cdot n\_b(\theta)}$, which is in the language, and $uv^ixy^iz = \theta b^i c^{i\cdot n\_a(\theta)} c^{n\_a(\theta)\cdot n\_b(\theta)}$ is also in the language.

In other words, any string where I seperate the ab's from the c's I can prove that even by taking a v of size 1, I will always find u,v,x,y,z substrings that match.

At this point I don't really know how to construct a word any more to disprove the pumping lemma. It's very obvious that there has to be one, but not so obvious what I should look at.

Any help would be greatly appreciated.

# Answer
i figured it out

$w = (ac^pb)^p $ cannot be split.

in the case that vxy consists of only a's and b's $uv^0xy^0z $ would have less a's and b's but not less c's.

in the case that vxy consists of only c's $uv^0xy^0z $ would have less c's but not less a's and b's.

in the case of a combination it might have an a or a b or both. if it has an a, the number of c's needs to increase by p, but $|vy| \le p$ and we'd need p + 1 terminals. for b the same holds, and for an a and a b it would need even more c's.

so we cannot split this word into 5 substrings u,v,x,y,z such that $uv^ixy^iz$ is in L
> 1 votes

# Answer
Assume $L$ is context free, thus it satisfies the pumping lemma. Call the constant of the lemma $p$. Pick the string $\sigma = a^p b^p c^{p^2} \in L$, and $\lvert \sigma \rvert = p^2 + p \ge p$. By the pumping lemma, you can write $\sigma = u v w x y$ so that $\lvert v w x \rvert \le p$, $x, y$ not both $\epsilon$, such that for all $k \ge 0$ it is $u v^k w x^k y \in L$. Now consider all possible ways to break up $\sigma$ complying with the conditions. By the length condition, $v w x$ is at most two types of symbols. But then repeating $v$ and $x$ unbalances at least the number of times the third symbol appears

We are forced to conclude that no division works, the language doesn't comply with the pumping lemma. It can't be context free.
> 0 votes

---
Tags: formal-languages, context-free, pumping-lemma
---


title: Solving a peculiar recurence relation

text:
# Question
Title: Solving a peculiar recurence relation
Given recurrence:

> $T(n) = T(n^{\frac{1}{a}}) + 1$ where $a,b = \omega(1)$ and $T(b) = 1$

The way I solved is like this (using change of variables method, as mentioned in CLRS):
Let $n = 2^k$

$T(2^k) = T(2^{\frac{k}{a}}) + 1$

Put $S(k) = T(2^k)$ which gives $S(\frac{k}{a}) = T(2^{\frac{k}{a}})$

$S(k) = S(\frac{k}{a}) + 1$

Now applying Master's Theorem,

$S(k) = \Theta(log\_2(k))$

$T(2^k) = \Theta(log\_2(k))$

$T(n) = \Theta(log\_2log\_2(n))$

I believe my method is incorrect because $a = \omega(1)$ doesn't necessarily mean that $a$ is a constant (or is it ?) and hence Master's Theorem is not applicable. Following the same line of reasoning, this also means that $b$ may not be a constant, but that would make "$T(b) = 1$" condition meaningless. Can anyone help clear out my misconceptions (if any) ?

Thanks

# Answer
In my opinion the problem statement seems poorly posed. It's not clear what is meant by the problem statement.

Normally, if we write $a$ or $b$ the assumption is that they are a constant: they do not depend on $n$. If they are intended to be a function of $n$, then they should be written as $a(n)$ or $b(n)$. Since that wasn't done, the only assumption I can see that makes sense is to assume they are constants. But then if they are constants, then writing $a,b = \omega(1)$ doesn't seem to me to make sense.

So, I suggest you go talk to your instructor to ask them what they had in mind and how one should interpret the question. We can't solve the question until we know what the question is asking.

Basically, I am validating that the confusion you are having seems reasonable: it seems reasonable to me to be confused about that, as I find the problem statement confusing.
> 2 votes

---
Tags: algorithms, asymptotics, runtime-analysis, recurrence-relation, master-theorem
---


# Question
Title: The PDA have to finish reading the input?
I have PDA which has final state that accept 'c' char, and there isn't any cross to other state. The input abca will accept, because there is 'c', or the PDA would stuck?

# Answer
> 2 votes
I think the PDA would stuck as to accept the input string "abcd", the complete input string needs to be read. But your PDA will work only till 'c' is read and get stuck when it finds another letter 'd', but has no transition state.

---
Tags: automata
---


title: Why L' is not regular?

text:
# Question
Title: Why L' is not regular?
$$L'=\\{ww|w\in L\\}$$

I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular.

How can I give such an example if according to closure properties for concatenation $L1L2$. each of them is regular,concatenation gives me a regular output.

# Answer
I think that you are having trouble distinguishing the difference between regular and non-regular languages, so I try to give a short explanation before I give you an example.

We call a language $L$ regular if it can be decided if a word is in the language with an algorithm/a machine with constant (finite) memory by examining all symbols in the word one after another. E.g. the language consisting just of the word $ab$ is regular, as we can decide whether a word is in it without requiring arbitrary amounts of memory; you just check whether the first symbol is $a$, whether the second is $b$, and whether any more symbols follow. The construct of a finite-state machine is used to prove whether a language is regular or not.

So if we take $L\_1 = \\{a^nb \space | \space n \in \mathbb{N}\\}$; this is a regular language as you don't need arbitrary amounts of memory, the concatenation $L\_1' = \\{ a^nba^nb \space | \space n \in \mathbb{N} \\}$ would be non-regular as you need a memory to 'remember' how many $a$'s the first one has as the second $a$ is required to have the same amount.

Now as gnasher729 already stated, $L\_2 = \\{a^\*b\\}$ is regular and $L'\_2 = \\{ a^\*ba^\*b\\}$ would also be regular as we do not have to remember how many $a$'s there are. We only need a finite-state machine to check if the last $a$ in each part is followed by one $b$.
> 2 votes

# Answer
Let L = a\*b. LL is regular ($a^nba^mb$). But the language you are asked to check is $a^nba^nb$ where the two n’s are the same. There are plenty of proofs in the last days here that you can adapt. And Myhill-Nerode is super easy.
> 1 votes

---
Tags: automata, regular-languages, regular-expressions, closure-properties
---


# Question
Title: Converting a function with single parameter to a function with multiple parameters
I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows:

Given a string or a list, do an aggregation operation on each of its elements. Here in each of these elements we apply some recurrence to solve it.

An example of one such problem is below.

---

**Problem:** Given n integers return the total number of binary search trees that can be formed using the n integers

To solve this problem, I define a recurrence relation as follows:

```
f(n) = 1 // if n = 0
f(n) = ∑ f(i) * f(n-i-1) where 0 <= i <= n-1

```

This works and I get the correct answer however I want to modify the function a bit.

Instead of expressing the function in terms of `f(n)` I want to express it in terms of `f(n, i)` so I can remove the summation. However I am unable to do it correctly.

---

**Code**

My code to solve the problem by defining the recurrence in terms of f(n) is as follows: (I am aware it can be optimized by DP but that is not what I am trying to do here)

```
public int f(int n) {
    if(n == 0)
        return 1;

    int result = 0;
    for(int i = 0; i< n; i++)
        result += f(i) * f(n-i-1);
    return result;
}

```

I want to remove that for loop and instead express the function in terms of `f(n,i)` instead of `f(n)`.

---

**Question**

1. How to convert the recurrence shown above from `f(n)` to `f(n,i)` and remove the summation?
    * Here 'n' is the size of the list of element and 'i' is the ith element in the list that we choose to be the root of the tree.

# Answer
You could do it by making the second parameter of your function function like the index of the summation, and recursively increment this parameter as long as $0 \leq i \< n$.

$$f(n, i) = \begin{cases} 1 & \text{if } n =0\\ f(i, 0)\cdot f(n-i-1,0) + f(n, i+1) & \text{if } 0 \leq i \< n\\ 0 & \text{otherwise}\\ \end{cases}$$

Then $f(n, 0)$ gives you the answer you want.
> 0 votes

---
Tags: algorithms, computability, recurrence-relation, recursion, functional-programming
---


# Question
Title: Using MyHill Nerode theorem to prove a language is non-regular
The language is $S = (a^nb^m | n \geq m)$.

I'm having trouble understanding MyHill Nerode theorem. Basically if I want to use MyHill Nerode theorem to prove $S$ is non-regular, I have to show that there are infinitely many equivalence classes. So in this case if I choose $S = a^n$ is simply not working since $n \geq m$ and thus $a^mb^m \in S$. So I think I have to pick $S = b^m$ and $a^nb^m \in S$ but $a^nb^n \notin S$. Does my assumption accurate or any suggestion?

# Answer
The classes are defined over words of the alphabet such that two words $x, y$ are equivalent if for any word $z$ we have $xz \in L$ if and only if $yz \in L$.

Consider for each $n\in \mathbb{N}$ the class $C\_n$ defined as $$C\_n = \\{x \in S : \\#\_b(x) \geq 1 \text{ and } \\#\_a(x) -\\#\_b(x) = n\\}.$$

Note that for each word in this class we can append exactly the strings $b^i$ where $i \leq n$. So for two different values $n\_1$ and $n\_2$ where $n\_1 \< n\_2$ the word $b^{n\_2}$ is a valid suffix to words in $C\_{n\_2}$ but not in $C\_{n\_1}$. Hence we have infinitely many such classes. Words ending with the letter $a$ accept additionally more $a$s and hence do not even belong to these classes and we have even more classes. Since we have infinitely many classes, the language is not regular.
> 0 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: NP-complete problem whose corresponding optimization problem is not NP-hard
For this question I will refer to$\ NP-hard$ problems as those that are at least as hard as$ \ NP-complete$ problems. That is, a problem$ \ H$ is$\ NP-hard$ if there is an$ \ NP-complete$ problem$\ G$, such that$\ G$ is reducible to$\ H$ in polynomial time.$\ NP-hard$ problems are not restricted to decision problems and are not necessarily in$\ NP$.

Considering the above, is there any optimization problem$\ L$ such that$ \ L \notin NP-hard $ and whose corresponding decision problem is$ \ NP-complete$?

For example, consider the case for the travelling salesman problem. (TSP)

> **Optimization problem:** Given a list of cities and the distances between each pair, what is the shortest path that visits each city and returns to the original city?
>
> **Decision problem:** Given a list of cities, the distances between each pair and a length$ \ L$, does there exist a path that visits each city and returns to the original city of length at most$\ L$.

It is well known that the decision problem of TSP is$ \ NP-complete$ and its corresponding optimization problem is$\ NP-hard$.

To sum up, what is an example of a$\ NP-complete$ problem whose corresponding optimization problem lies outside the class$\ NP-hard$? Perhaps, it is$\ EXPTIME$.

# Answer
> 2 votes
Take a look at Bellare and Goldwasser, "The complexity of decision vs. search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119. It discusses the issue at length. Perhaps a bit more readable is the class note by Bellare, "Decision versus search".

# Answer
> 1 votes
Not if the objective function is computable in polynomial time. Suppose the optimization problem, $H$, is to find $x$ that maximizes $\Phi(x)$, where $\Phi$ is some computable function (one could take this as the definition of an optimization problem, in which case all optimization problems can be put into this form). The corresponding decision problem is, given $t$, test whether there exists $x$ such that $\Phi(x) \ge t$. Call this decision problem $G$. Suppose $G$ is NP-complete, and moreover suppose that $\Phi$ can be computed in polynomial time. Then $G$ is reducible to $H$ in polynomial time (to solve $G$, solve $H$ to find the optimal $x$, then test whether $\Phi(x) \ge t$). It follows that if the associated decision problem $G$ is NP-complete and if $\Phi$ can be computed in polynomial time, then the optimization problem $H$ is NP-hard.

---
Tags: complexity-theory
---


# Question
Title: Reducing vertex cover to minimal vertex cover
What is a quick and a elegant way to reduce vertex cover to minimal vertex cover?

Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? since minimal vertex cover is essentially $min{f(x)|x\in VertexCover(G)}$

Graph is basic if it matters, no weights, and it is undirected

thank you for helping

# Answer
> 1 votes
Search for Bellare and Goldwasser "The Complexity of Decision vs. Search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119, or Bellare's class note on the matter.

---
Tags: complexity-theory, turing-machines, computability, reductions, vertex-cover
---


# Question
Title: Context-free grammar for ${a^n b^n a^n}$
I am trying to figure out a formal grammar for the above language. This language describes palindromes, so it is context-free, if I am not wrong. I came up with a context-sensitive grammar, but I can not find a context-free one. Any ideas?

# Answer
> 4 votes
The languages of all palindromes is context-free.

That does not implies that any language that contains only palindromes is context-free. For example, many language over the unary alphabet $\\{a\\}$ are not context-free. In fact, they can even be non-context-sensitive or undecidable. Note that any word over a unary alphabet is a palindrome.

In particular, the language of all words like $a^nb^na^n$ is not context-free. The rough intuition to understand why it is not context-free is that a PDA cannot remember two unbounded independent relations. You can either use the pumping lemma to prove that fact.

**Exercise.** Give an example of a unary language that is not context-free.

# Answer
> 0 votes
How about $\\{a^{\Sigma(n)} \colon n \ge 1\\}$, where $\Sigma$ is Radó's noncomputablr busy-beaver function?

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: Is it decidable if there exists some input such that the TM makes at least five moves?
I am reading this excerpt from Ullman's book:

I have following doubts:

1. (related to red underline) TM can make 5 left moves or 5 right moves. So it will need at max 11 cells. Then how it says 9?
2. (related to green underline) Whats the significance of "finite"? Due to 9 (or 11 if I was correct in point 1)?
3. (related to blue underline) I am not able to understand the given proof. I tried it myself: I will run TM on all length 1 to 5 strings. If it makes 5+ moves on any of these strings, then "accept", else "reject". Hence decidable. Is my interpretation / approach correct? If correct then what was the significance of thinking about those nine cells?

# Answer
> 1 votes
1. It's 9 because it doesn't matter what symbol we land on after move 5.
2. It's finite because the number of cells is 9, yes. The significance is because otherwise the algorithm in point 3 wouldn't finish.
3. All strings of length 9, with the starting point in the middle. "Five or fewer" is an error, I believe.

# Answer
> 0 votes
If the machine does exacly 5 moves, it reads at most 5 symbols. If after 5 moves it is still going, it does more than 5 moves on a tape starting with that string. So you have to check a finite set of possible inputs (strings of 5 symbols), each for a finite number of steps (5 in this case). So you can always answer "yes" or "no" in finite time, this is recursive.

---
Tags: formal-languages, automata, undecidability
---


# Question
Title: Algorithm to enumerate all complete schedulings of finals tests?
I'm creating an app that receives some map between finals and the respective periods during which they are held and a student's required finals. I was wondering if there was an algorithm to enumerate all *complete* schedulings of these finals. Concretely, I have a list of finals for a specific student and each $F\_i$ has a list of periods $P\_i$ that they are held. In my specific use case, there are $8$ periods.

$$ \begin{align} F\_1 &\rightarrow \\{P\_1, P\_2, P\_8\\} \\ F\_2 &\rightarrow \\{P\_4, P\_7\\} \\ F\_3 &\rightarrow \\{P\_4\\} \end{align} $$

And I want to find all assignments of periods to finals that are non-overlapping and *complete*, i.e. the student can attend all finals. One such assignment could be:

$$ \begin{align} P\_1 &\rightarrow F\_1 \\ P\_4 &\rightarrow F\_3 \\ P\_7 &\rightarrow F\_2 \end{align} $$

This is *complete* because all finals are associated to a period and the periods are non-overlapping. Another assignment could be $P\_4 \rightarrow F\_3, P\_7 \rightarrow F\_2, P\_8 \rightarrow F\_1$. My question is then, how could I enumerate all these assignments? I was thinking of a greedy approach whereby I choose a period starting with the finals with the fewest amount of available periods, the choosing for the next-most restricted final. But that only gives me one particular working schedule, not *all* valid schedulings.

# Answer
You're asking to enumerate all maximum matchings in a bipartite graph. Unfortunately that problem is #P-complete, so there is unlikely to be any efficient algorithm that works on arbitrary size graphs.

There might be algorithms that work well enough for your situation, given the small numbers you're dealing with. For instance, a simple approach is to use a backtracking search. First nondeterministically choose a period for final $F\_1$ (out of all possibilities). Next choose a period for final $F\_2$ (out of all possibilities, excluding the periods that have already been chosen), and so on. If at any point there are no legal choices available (e.g., you want to choose a period for $F\_i$ but all options have already been filled with a final), terminate. Now replace the nondeterministic choices with branching over all possibilities, in a breadth-first or depth-first search, and that should provide a way to enumerate all valid schedules.

See also Counting and finding all perfect/maximum matchings in general graphs and https://en.wikipedia.org/wiki/Matching\_%28graph\_theory%29#Counting\_problems for references to the literature on the general problem.
> 3 votes

---
Tags: algorithms, scheduling
---


title: How to learn how CPU works in details

text:
# Question
Title: How to learn how CPU works in details
I've watched multiple videos and read posts regarding modern cpus and how they work.

However, those ones very rarely touch the problem on the very basic level. Like I've read about transistors and stuff but I would like to spend (a lot I guess) time to actually understand how e.g. programming a math operation like 5^5 is calculated by cpu hardware.

Do you have any ideas where to start?

p.s. my uni background is econometrics which ended up in machine learning job. Unfortunately I have no CS knowledge.

Kind Regards, Matt

The recommended online resource I found was: Hoow do it know

# Answer
Today's CPUs are incredibly complex beasts. Sure, you can go rummage in computer architecture books and get a rough idea how a *very simple* CPU works. Understanding in detail how the CPU in your PC (or even your smartphone) works will require a lifetime, if not more. I suspect noone at Intel/AMD really undestands their latest CPU fully.

For example, today's processors take instructions from RAM, translate them into microinstructions internally, reorder and schedule those working even on several copies of the programmer-visible registers in parallel where possible (doing more or less the job of an optimizing compiler), and finally executing the resulting stream(s) of microinstructions.

Today's CPUs are much, much faster than RAM (in the time required to fetch a word from memory they can execute hundreds of instructions). Cache memory, and it's efficient use, predicting what will be read next, is crucial. Another area of significant complexity.

Add circuitry to compute the various operations, including floating point and assorted functions, like square roots and trigonometric functions. A box marked "floating point unit" right there.

And this doesn't yet consider the GPU that is integrated in some models...
> 2 votes

# Answer
There are a few good standard textbooks on this topic.

*Computer Organization and Design: The Hardware/Software Interface* by Patterson and Hennessy is extremely popular. I believe it's up to the 5th edition now.

But if you've never even seen a logic gate before, it may be worth starting with digital logic design, and sequential circuits in particular. There are a lot of videos and courses out there. My textbook was *Digital Design* by M. Morris Mano. You could do a lot worse than that book, but I'm not sure if there's anything more common today.
> 0 votes

---
Tags: cpu
---