# Question
Title: Proving P = NP without mathematical statements / computer program
This is my first post after being a passive user for some time now. I wish to ask some questions if I may. I am not a mathematician but my question relates to the field of maths/computer science. In particular, the P vs NP problem. I am aware that this is a problem that elite professionals have not yet been able to solve ...

Regardless, I would like to ask:

If a person who is neither a mathematician nor a programmer were to come up with a flowchart or a series of steps written in basic English that allegedly provides a solution to one of the P vs NP problem, would that be counted as 'proving' that P = NP .. in order to claim the Clays Institute prize :) ? Or is it a must for one to write the solution as mathematical proofs / computer program?

Thank you.

# Answer
"No", you can use "basic English".

If you succeeded, you would have created a **constructive proof**. Proofs in mathematics are often a mix of "basic English" as you call it and mathematical formulae, but they need not contain either to be a valid proof.

Suppose you have such a flowchart, what you need to prove—i.e. argue—is, that your algorithm works for ***every*** problem instance. The way you do that is entirely up to you, as long as the proof is unambiguous and all the premises you assert have been shown to be true.

Having done that, you have a *mathematical proof* in your hands. So really, I should have said "***Yes***" at the beginning, you do need a *mathematical proof*.
> 16 votes

# Answer
A Turing machine, it must be remembered, *is* a kind of flowchart. So is the structure of a computer program generally. So turning "a flowchart" into a formal answer to the problem should be fairly easy, if it actually did work. Indeed, if one started with a terribly formal answer to **P** versus **NP**, most computer scientists would try to find a formulation of it which did come as close as possible to a plain english description in order to get as strong an understanding of the solution as possible.

But there is a fundamental problem with the sort of question that you're asking. What does it mean for someone who would be able to solve **P** versus **NP** — and by showing that they are equal, no less — to not actually be either a computer scientist or a mathematician? Perhaps they are not employed professionally as a computer scientist or mathematician, but this is beside the point if they have the skill to solve what some (Scott Aaronson, for example) describe as the most important mathematical problem we've ever considered. If someone has the training (or has even self-taught) to successfully tackle the problem, *and also to clearly communicate the solution to others* by identifying the major sub-routines and their roles in solving e.g. SAT or HAMPATH, then whether they are employed or even have degrees is an irrelevant detail; they are nevertheless in that case a mathematician or a computer scientist. Better still if they can describe how their solutions overcome classic obstacles such as oracle results, such as oracles *A* for which **P***A***NP***A* (or the opposite) by showing specifically what sorts of structure in the problem the algorithm takes advantage of, which would not be accessible in the oracle model. The problem, however, is that most people who dream of solving **P** versus **NP** *as amateurs or outsiders* seem to lack the communication skills to actually describe their work adequately, or (by virtue of not having read enough) they are unaware of results which would make their approach to solving the problem doomed from the start.

As with all dreams of glory these days, there is a basic problem with the fantasy of being the one to resolve **P** versus **NP**. The problem is that it's bound to be nearly impossible. Not *actually* impossible, mind you, or at least not necessarily impossible; just nearly so. As someone bright with ambition, it is possible for one to lose sight of the fact that there are many other bright people: many of whom have also thought about the problem; and many of whom are brighter than oneself, even by a couple of orders of magnitude. And that there have been such bright people for as long as the problem has been around; and yet it remains unsolved. Yes, it's possible in principle that everyone is thinking about it the wrong way, and have been for decades. But is that *really* particularly likely? Nobody should expect themselves to be the one person who can spot the one sign-error that everyone else is making, because if everyone else is making that error then there must be something about the problem that will lead one to make the same mistake. Or — in the more likely event that the reason why the problem remains unsolved is *not* that people keep making simple mistakes or haven't yet thought of the one simple trick that dissolves the whole thing — what makes the problem fundamentally difficult is essentially an objective difficulty of the problem, and no clever dancing steps will allow one to simply waltz gracefully past all obstacles; that what is required is an approach which is not merely novel, but quite profound, identifying subtle structures that there was good reason for nobody to have seen before. The sort of structure which one is most likely to spot by thinking continuously about the problem for years.

If you want to be realistic about what it would take to solve the **P** versus **NP** problem, you might compare it to similarly famous breakthroughs in the past few decades, such as the proofs of the four-colour theorem, Fermat's Last Theorem, or the Poincaré conjecture. They might have simpler proofs someday, but the original proofs take you far into the wilderness to get you to the end (or in the case of the Four Colour theorem, the route is very long and repetitive). There's no particular reason to suspect that **P** versus **NP** will be different; so that if in the end it *is* resolved by an amateur, chances are extremely strong that it would be by someone with similar background knowledge and awareness of techniques of someone who is academically trained. Any realistic amateur who dreams of solving **P** versus **NP** would do well to keep that in mind.
> 19 votes

# Answer
A proof that P = NP might get accepted by a mathematical journal, but it will never be accepted by the elite professionals. The reasons is that they know that P != NP (at least for all practical purposes). They also know that it is unbelievable difficult to prove this, so even a proof that P != NP will be received with a healthy amount of skepticism by the elite professionals.

The elite professionals have more elaborate reasons than that many bright minds tried and failed to construct a polynomial algorithm for NP or prove N != NP. However, they reasonably expect that this argument should be the most convincing for a layperson. They are probably right that reference to barriers related to relativizing proofs, natural proofs or algebrizing proofs are rarely convincing for a non-expert. If too many "amateurs" try to resolve P vs NP in a certain way (for example by logical resolution, or by reducing it to a linear programming problem), then somebody will go through the pain (this sometimes takes years) to prove that this specific angle of attack is likely doomed to fail.

**Edit** I'm delighted that this answer continues to attract (negative) feedback. Let me therefore replace the second part of the answer (which seems unrelated to the feedback, but may distract from the main point) by the following quote from Truth vs Proof:

> We could remain agnostic, saying that we simply don’t know, but there can be such a thing as too much skepticism in science. For example, Scott Aaronson once claimed that in other sciences P != NP would by now have been declared a law of nature. I tend to agree. After all, we are trying to uncover the truth about the nature of computation and this quest won’t go any faster if we insist on discarding all evidence that is not in the form of mathematical proofs from first principles.

This change is not intended to reduce the amount of feedback, but to make it perfectly clear that this answer is serious about the fact that the experts "know that P != NP", even so they can't proof it.

---

**23 Nov 2013** Thanks again for all the feedback. For the record, the answer now has 7 downvotes, 1 upvote and 14 comments (8 by me). Due to the amount of comments, interesting references and justifications given in the comments are hidden, so I decided to add some of them here:

* As Gödel himself wrote to von Neumann, if P=NP were true "for all practical purposes", then his incompleteness theorem would only be true in theory, but effectively false in practice.
* In his 1971 paper, Stephen Cook ... unable to produce counterexamples for the Davis-Putnam procedure (solved by Haken 1985). Today, many techniques, results and counterexamples are available for "disproving" proposed efficient NP-solvers. Also P = NP contradicts the "law of conservation of difficulty", the "qualitative infinitary \<-\> quantitative finitary" correspondence, ...
* A long time ago, Scott Aaronson wrote this comment:

> anonymous: *You claim (as being fact!) that 3SAT is a language in NP that cannot be computed in polynomial time. But you cannot prove it. Is that your scientific method?* Yes. As a firm believer in science and reason, I strive to distinguish clearly between what I can prove and what I merely know is true.
* Scott is famous for trying to demonstrate what it means that he "knows" something, for example by betting $200,000: scottaaronson.com/blog/?p=458
> -6 votes

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


# Question
Title: randomized algorithm for checking the satisfiability of s-formulas, that outputs the correct answer with probability at least $\frac{2}{3}$
I'm trying to practice myself with random algorithms.

Lets call a CNF formula over n variables s-formula if it is either unsatisable or it has at least $\frac{2^n}{n^{10}}$ satisfying assignments.

I would like your help with show a randomized algorithm for checking the satisfiability of s-formulas, that outputs the correct answer with probability at least $\frac{2}{3}$.

I'm not really sure how to prove it. First thing that comes to my head is this thing- let's accept with probability $\frac{2}{3}$ every input. Then if the input in the language, it was accepted whether in the initial toss($\frac{2}{3}$) or it was not and then the probability to accept it is $\frac{1}{3}\cdot proability -to-accept$ which is bigger than $\frac{2}{3}$. Is this the way to do that or should I use somehow Chernoff inequality which I'm not sure how.

# Answer
> 8 votes
Basic idea: Pick a random assignment and check it. Then, repeat it many times. Even if one of the assignments satisfies the formula you answer "YES" (otherwise, you answer "NO")

We know that the input formula is "simple": in plain words it means that either it is not-satisfiable **or** it has "many" satisfying assignments. If it is not satisfiable - no matter what assignment(s) you choose, it will never satisfy the formula. Therefore, the above algorithm always answers correctly for such inputs, and from this point and on we consider **only** satisfiable inputs.

If the input is satisfiable, what is the probability that a random assignment satisfies it?

Let $\varphi$ be a CNF over $n$ variables with more than $2^n/n^{10}$ satisfying assignments, then $$ \Pr\_{x\sim U}\[ \varphi(x)=T\] \ge \frac{2^n/n^{10}}{2^n}$$

Now we repeat it $k$ times (you'll have to pick $k$ carefully. Let's do it later). Each time we pick a random $x$. Let $E\_i$ be the event that in the $i$-th instance $\varphi$ is satisfied. What is the probability that we find out at least one satisfying assignment after $k$ tries?

It is $\Pr\[\bigcup\_{i=1}^k E\_i\]$. We know that $\Pr\[E\_i\] \ge 1/n^{10}$, and you can use standard linearity (of independent events) to work it out.

Final step - find the (minimal) $k$ that makes $\Pr\[\cup\_k E\_i\] \ge 2/3$ as required.

*Bonus question:* how low can you make $k$ (and make your algorithm more efficient) if you analyze the above using Chernoff's inequality?

# Answer
> 4 votes
Your suggestion doesn't work. When the formula is unsatisfiable, your algorithm outputs the correct answer with probability $1/3$ only.

Hint: If a formula has $2^n/n^{10}$ satisfying assignments, what's the probability that a random assignment is satisfying?

---
Tags: complexity-theory, time-complexity, randomized-algorithms
---


# Question
Title: Pumping lemma problem - Choosing the right string to pump
I have a problem finding the right string to pump for the following language:

$$L\_1 = \\{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge 0\\}$$

Which string should I choose to pump? The problem is that I don't know how to handle the fact that I have $p+q$ and $q+r$?

Can I choose: $$Z = a^{2n}b^nc^nd^{2n}e^s$$

Thanks in advance.

# Answer
> 2 votes
If $k$ is the *pump length* from the regular pumping lemma choose $w=c^ke^k$. Clearly, $w\in L\_1$, but if you pump you have to change the number of $c$'s while leaving the $e$'s unaltered. Hence after pumping the word is no longer a member of $L\_1$.

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


# Question
Title: Progress of algorithms in problem spaces
Continuing in the vein of two prior questions (1) and (2), we started with sorting, where we had

1. a set of $n!$ input possibilities
2. a goal space of only one element consisting of the one correct sorted sequence

We then arrived at a generalized argument which I'll alter slightly and call *A*:

1. Define a space of input possibilities
2. Define the goal space, a subset of the input space
3. Reason about constraints in order to set a lower bound

Three Questions: given that there are quadratic algorithms for sorting,

1. Can we conclude for the quadratic sorting algorithms, where we have an input space of $n!$ input possibilities and roughly $n^2$ steps, that there are $O(n!/n^2)$ possibilities removed from the search space per step on average?
2. Let's say we're given a problem formalizable in the form of argument *A* above where the input space is exponential in terms of the size of the input, $O(2^n)$, and the problem is solvable in polynomial time, $O(n^c)$, for some constant $c$. Can we conclude there are $O(2^n/n^c)$ possibilities removed from the search space per step on average?
3. Can we at least conclude that a $O(2^n)$ problem cannot be solved in polynomial time by removing one element from the input space per step?

# Answer
1. Yes and No. If you see this as "amortized" number of possibilities removed in each step, then yes (follows trivially since you need $n^2$ time but have a search space of $n!$), but it is very difficult to formalize a notion of how many possibilities in each step are removed. You would need a notion of what a "step" is. An elementary operation, like an addition? Then how does one addition in the middle of, for instance, bubble sort reduce the search space? Instead, you have some kind of "checkpoints" during the algorithm at which the search space gets smaller, for instance when you find the 1st element, the 2nd, and so on. A concrete counter example to your idea is an algorithm that uses $n^2$ time in a dummy loop, and then solves the problem. In the first $n^2$ steps therefore, the solution space does not get smaller.
2. No, see above.
3. Yes, trivially?
> 3 votes

---
Tags: proof-techniques, lower-bounds
---


# Question
Title: Non-deterministic algorithm for solving figure of 8
I am struggling in trying to figure out a non-deterministic algorithm for the following problem.

Consider the following problem, called the ﬁgure-of-eight problem (FOE). An instance is an undirected graph $G = (V,E)$ with vertices $V$ and edges $E$. $G$ is a yes-instance if there is a sequence of vertices $(v\_{0},v\_{1},...,v\_{k+1})\ (some\ k \geq 6)$ such that

• Each pair $(v\_{i},v\_{i+1})$ is an edge $(each\ i \< k − 1)$ and $(v\_{k−1},v\_{0})$ is an edge.

• Every vertex in $V$ occurs at least once in the sequence.

• There is $j$ with $2 \< j \< k − 2$ such that $v\_{0} = v\_{j}$.

• No other vertex in the sequence is counted twice, i.e. if $v\_{s} = v\_{t} (any\ s,t \< k)$ then either $s = t$ or ${s,t} = {0,j}$.

If there is no such sequence of vertices then $G$ is a no-instance of FOE.

Thanks

# Answer
> 2 votes
If you want to prove that this problem is in NP, then all you have to do is to come up with a polytime algorithm that verifies the correctness of a solution. I.e., in polynomial time, verify that a given sequence satisfies the conditions you wrote.

This should also help you in actually construct the non-deterministic algorithm.

---
Tags: algorithms, complexity-theory, graphs, nondeterminism
---


# Question
Title: Generating a adjacency matrix representing a DAG
Does anyone have a pointer to a resource or, even better, a tip to provide on how to efficiently generate a very large matrix representing a connected graph.

Graph can be randomly created although I would ideally generate a graph of desired size and topology similar to what one can do with JGraphT.

My general intent is to create a very large graph representation (billions of nodes and edges) in parallel by first generating an adjacency matrix to ensure connectedness and then create a representation (RDF, etc) in parallel.

Any further suggestions or alternative approaches are welcome.

# Answer
Yes there is an easy way to generate a random DAG. If a graph is a DAG it can be separated into levels or ranks. The idea is to rank the nodes and randomly generate edges from lower ranked nodes to higher ranked nodes. A little bit of Googling finds the exact same question asked on stackoverflow a few months ago (with sample code!).

My only concern is that an adjacency matrix representation for a graph with billions of nodes/edges won't fit in memory. However, it's possible I misunderstood your intent in that part of the question.
> 1 votes

---
Tags: graphs, adjacency-matrix
---


# Question
Title: Importance of recursion in computability theory
It is said that computability theory is also called recursion theory. Why is it called like that? Why recursion has this much importance?

# Answer
> 22 votes
In the 1920's and 1930's people were trying to figure out what it means to "effectively compute a function" (remember, there were no general purpose computing machines around, and computing was something done by people).

Several definitions of "computable" were proposed, of which three are best known:

1. The $\lambda$-calculus
2. Recursive functions
3. Turing machines

These turned out to define the same class of number-theoretic functions. Because recursive functions are older than Turing machines, and the even older $\lambda$-calculus was not immediately accepted as an adequate notion of computability, the adjective "recursive" was used widely (recursive functions, recursive sets, recursively enumerable sets, etc.)

Later on, there was an effort, popularized by Robert Soare, to change "recursive" to "computable". Thus we nowadays speak of computable functions and computably enumerable sets. But many older textbooks, and many people, still prefer the "recursive" terminology.

So much for the history. We can also ask whether recursion is important for computation from a purely mathematical point of view. The answer is a very definite "yes!". Recursion lies at the basis of general-purpose programming languages (even `while` loops are just a form of recursion because `while p do c` is the same as `if p then (c; while p do c)`), and many fundamental data stuctures, such as lists and trees, are recursive. Recursion is simply unavoidable in computer science, and in computability theory specifically.

# Answer
> 1 votes
Computability theory is the study of computable functions :-).

Such functions are usually (in this community) defined as functions that can be expressed with a Turing machine.

More formally a function $f: \mathbb{N} \mapsto \mathbb{N}$ is *computable* if there exist a Turing $T$ such that if the input to $T$ is $x = 1^n$ the output of $T$ is $1^{f(x)}.$

As it turns out if you define computable functions in this way (programs) they are equivalent to the set of functions one can obtain by using the rules described here. They are called recursive functions since one of the rules for obtaining such functions is a recursive definition (See the 5th rule on wikipedia).

So the reason why recursion theory has much importance is equivalent to the question of why are computable functions important. And the answer to the latter should be quite obvious :)

---
Tags: computability, terminology, history
---


# Question
Title: Which complexity classes are $\mathsf{RE}$?
Given some complexity class $\mathsf{C}$, I want to know if there exists a function (Turing machine) $F:\mathbb{N} \to \mathsf{C}$ such that, if $S$ is any set for which the problem $x \mapsto x \in S$ is in $\mathsf{C}$, then $F(n)$ is a Turing machine which (partially, if $\mathsf C = \mathsf{RE}$) decides $x \in S$ for some $n$.

Note that if $g$ and $h$ are two Turing machines that decide $x \in S$, then $F$ only needs to enumerate one of them (hopefully this makes the problem easier). Thus the title is a bit wrong, but kept as it is for lack of a better one.

Trivially, if $\mathsf{C}$ equals something in the Chomsky hierarchy, such machine $F$ exists (enumerating all grammars of the required type). I'm interested in the less obvious classes.

# Answer
Time-bounded classes can be enumerated. Suppose we want to enumerate all languages in P. Every language in P is accepted by some Turing machine $T$ running in time $f(n)$ for some polynomial $f$. We can construct a Turing machine $T'$ that emulates $T$ but also keeps track of the time, and stops after $f(n)$ steps. Every Turing machine of the form $T'$ accepts a language in P, and vice versa, for every language in P, we can construct such a machine $T'$. The machines $T'$ themselves can be enumerated by enumerating the simulated machines $T$ and the "timers" $f(n)$.

For a space-bounded class, you do something similar, keeping track of the space usage of the Turing machine. You also need to prevent infinite loops somehow, either using a timer or by keeping track of all positions encountered so far during the simulation.

Non-deterministic and randomized versions can also be handled this way, so for example, PH can be enumerated.
> 5 votes

# Answer
The codomain of $F$ should be Turing machines (or machines in some other particular model of computation) not the complexity class itself. You can't identify the machines that decide sets in a complexity class with the sets in the complexity class because it is not a one-one correspondence. Moreover a complexity class has various representations, you have to fix the representations of the sets in the complexity class (by fixing a model of computation) before discussing how to enumerate them.

Let $\tilde{C}$ be a representation of sets in the complexity class $C$, i.e. the sets decided by machines in $\tilde{C}$ belong to $C$ ($\tilde{C}$ doesn't need to be an r.e. set, e.g. $C = \mathsf{BPP}$ which we don't know any r.e. representation for, but it should be enumerable so we can consider it as a subset of $\mathbb{N}$). You want a function $F:\mathbb{N}\to \mathbb{N}$ s.t.

* for all $n\in\mathbb{N}$, $F(n) \in \tilde{C}$,
* for all $A \in C$, there is $n\in\mathbb{N}$ s.t. $L(F(n)) = A$,
* $F$ is computable.

So we have at least one representative for each set in $C$ and we can computably enumerate these representatives.

This is related to the question of being a *syntactic* complexity class. Most famous complexity classes turn out to be syntactic as is implied by Yuval's answer (it is open for other famous complexity classes like $\mathsf{BPP}$). If we have an efficient *universal simulator* for the complexity class then the class is syntactic. It is important to remember that we want machines that decide sets in the complexity class to decide them with reasonable resources.

ps: this is also known in literature as *recursive representability*, also sometimes referred to as *recursive indexing* of the complexity class (look also for computable in place of recursive).
> 2 votes

---
Tags: complexity-theory, computability
---


title: Pumping lemma problem

text:
# Question
Title: Pumping lemma problem
I need some help with the following question:

One of the languages

$$L\_1 = \\{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s \> t\\}$$ $$L\_2 = \\{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge 0\\}$$

is context-free and the other is not. Build a context-free grammar for the one that is. For the other one provide a proof that it is not regular, or that it is not context-free.

How do I approach this problem ? I think that L2 is context-free because no comparisions are made. L1 is not context-free.

Thanks in advance

# Answer
> 3 votes
You are actually wrong. I'll give you a hint for the grammar of $L\_1$. Rewrite it as $a^p b^r b^q c^{s-t} c^t d^t d^q e^r e^p$. Although I have no idea how the case $s = 0, q = 0$ (thus $q+t \< 0$) is supposed to work.

For $L\_2$ there is an implicit comparison $r \leq q+r$. Take $p = q = 0$ so that the string is $b^rc^sd^re^s$. You should be able to apply the lemma here easily.

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


# Question
Title: categories of registers and and storage in them
The Wikipedia article on processor registers mentions:

> Address registers hold addresses and are used by instructions that indirectly access primary memory.

Which addresses does this sentence refer to?

# Answer
> 1 votes
RAM addresses or addresses of I/O devices. For example, in x86 architecture an IP (instruction pointer) register holds the memory address of the next instruction that is going to be read and executed. This register cannot be accessed directly (it can be modified by jumps though). Also, in x86 an SP (stack pointer) register shows the top of the stack structure (mostly used to hold local variables of functions) and is implicitly modified by `push`, `pop`, `call`, `ret` instructions (and interrupts). Of course, there are more examples.

---
Tags: computer-architecture, memory-access
---


# Question
Title: Is it $\mathsf{NP}$-hard to decide whether $\mathsf{P}=\mathsf{NP}$?
> Is it $\mathsf{NP}$-hard to decide whether $\mathsf{P}=\mathsf{NP}$ ?

If so, what are the implications ? Is there result suggesting that it is the case ?

# Answer
A similar question is this:

> Is $(a \vee \neg b) \wedge (\neg a \vee b)$ $\mathsf{NP}$-hard?

The question itself doesn't make much sense, as $\mathsf{NP}$ (as well as $\mathsf{NP}$-hard) defines a set of languages, but $(a \vee \neg b) \wedge (\neg a \vee b)$ is (just like $\mathsf{P} = \mathsf{NP}$) a word, an element of a language, not a language itself.

But all in all... one can say that it is generally hard to prove (or disprove) $\mathsf{P} = \mathsf{NP}$, it might even be impossible (as discussed in the answer by Jernej).
> 8 votes

# Answer
You have to first understand what is the problem here. A problem is usually a relation between inputs and outputs. The complexity is a measure of difficultly for algorithms to obtain input from the output. A single instance of a problem like the one you have are trivial, since there *exists* an algorithm that would output the answer (whether it is provable, refutable, or neither). However from the practical point of view this is not of much use.

Asking for $\mathsf{NP}$-hardness of an instances is a confusion that is not uncommon among non-experts in theoretical computer science. The reason for this confusion is that in algorithms/complexity courses, many students mistakenly view $\mathsf{NP}$-hardness as "not solvable in practice" or "no algorithm". $\mathsf{NP}$-hardness does NOT mean that the instances of the problem cannot be solved in practice (take for example SAT), it neither means that there are no algorithms, and it doesn't even mean that there is no efficient/polynomial time algorithm for the problem ($\mathsf{P}$ vs. $\mathsf{NP}$ is still an open problem in theoretical computer science and it doesn't seem that we are close to answer it).

I am guessing that what you really want to ask is if it is possible to use computer to find the answer to $\mathsf{P}$ vs. $\mathsf{NP}$. But this is not a very precise question: what do we mean by using computers to solve an instance of a problem?

Let me try to clarify this: assume that I know the answer to the question, and I write a one line program that always outputs the same correct answer (e.g. the answer to the question is YES and my program is `cout<<"YES";`). Do we consider this as using computers to find the answer to the question? I would assume no.

Another situation to understand the issues: assume that I have a brute-force algorithm and it finds the answer after say 1 billion years. It is an answer after a finite time, so it is a constant time algorithm However it is not really useful for us, since presumably we want to know the answer in a reasonable amount of time (say before we die). What is a reasonable amount of time? It is not a precise concept.

In summery,

* a problem instance cannot be $\mathsf{NP}$-hard, an problem instance is trivial from complexity perspective (there *exists* an algorithm that outputs the correct answer in constant time, we know it is one of the 3 programs (always output "YES", always output "NO", always output "UNDECIDABLE") but we don't know which of these 3 programs correctly solves the problem.
* $\mathsf{NP}$-hardness is a theoretical concept for a general instance of problems, it doesn't imply that we cannot solved a problem on instances we care about in practice (SAT is $\mathsf{NP}$-hard but in practice SAT-solvers work amazingly well on instances that some industries case about and understanding why this is the case is an on-going research topic).
* in practice often we don't care about general inputs, we care about a specific subclass of inputs, and on those inputs we might be able to solve the problem. However we should understand that our algorithm will not work on general examples. Any algorithm that works well on some subsets of inputs needs to exploit some properties of those inputs. If we don't have any idea about the particular properties of our instance then we are in a situation similar to the general case inputs.
* when we don't know any particular property of an instance of a problem we think of it at that time as being hard as general case.

One final point: even if $\mathsf{P}=\mathsf{NP}$ and we can solve SAT and proof search for proofs of a given length efficiently (given $\varphi$ and $n$, is there a proof of length $n$ for $\varphi$ in theory $T$, think of $T$ as ZFC for simplicity), it is possible that it won't help much with finding a proof of that fact for various reasons, e.g.:

* although the statement is true, there is no proof of it, so current axioms of mathematics are incapable of settling the question positively or negatively,
* we have an efficient algorithm for searching for proofs of given length, however the constants in the running time of the algorithm are huge, so even though the algorithm is polynomial time, it is not a practical algorithm (e.g. running time is $10^{1000}n^{500}$).

And similarly if $\mathsf{P}\neq\mathsf{NP}$, it doesn't mean that there isn't a short proof of this particular statement in $T$.

However there is a point here as Godel wrote in his famous letter to von Neumann, if there is an algorithm that running in time say $n^2$ that checks if there is a proof of length $n$, then we can run this algorithm with a large enough $n$ such that we are sure no human being can find a proof longer than that. In other words, if the algorithm doesn't solve the problem by either finding a proof or refutation of that size, then there is no answer that can be obtained by humans. So it is *undecidable in practice* for humans although it might be provable or refutable.

See also my answer on MSE to Solving P vs NP with computer.
> 7 votes

# Answer
It can be the case that *there is no proof of $\mathsf{P} = \mathsf{NP}$ and no proof of $\mathsf{P} \ne \mathsf{NP}$*. Hence there will be no algorithm to decide whether $\mathsf{P} \overset{?}{=} \mathsf{NP}$.

So we don't kniw if there is a proof for $\mathsf{P} = \mathsf{NP}$ or $\mathsf{P} \neq \mathsf{NP}$, let alone an algorithm to decide if the equality holds or not (in a way proofs are algorithms).

So there is not much sense in discussing the complexity of such an algorithm (if it exists).
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Most efficient known priority queue for inserts
In terms of asymptotic space and time complexity, what is the most efficient priority-queue? Specifically I am looking for priority queues which minimize the complexity of inserts, it's ok if deletes are a little slower.

<sub> If you're looking for a survey of priority-queues which minimises complexity of deletes over inserts, see: Does there exist a priority queue with $O(1)$ extracts?. </sub>

# Answer
> 4 votes
### Worst-case complexity

**Insert**: $\mathcal{O}(1)$

**Find-min**: $\mathcal{O}(1)$

**Decrease-key**: $\mathcal{O}(1)$

**Delete**: $\mathcal{O}(\log \log n)$

**Space**: $\mathcal{O}(n)$

### Proof

> THEOREM 1. *We can implement a priority queue that with n integer keys in the range $\[0 , N )$ in linear space supporting* **ﬁnd-min**, **insert**, *and* **dec-key** *in constant time, and* **delete** *in $\mathrm{\mathcal{O}(log\ log\ min \\{n, N\\})}$ time.*

Which is established with a combination of:

> LEMMA 3. *Let $\tau(n, N)$ be the* **delete** *time for a priority queue for up to $n$ integers in the range $\[0 , N)$ supporting* **insert** *and* **dec-key** *in constant time. Then $\tau ( n, N ) \le τ ( N, N)$. This holds whether $\tau$ is amortized or worst-case.*

and:

> THEOREM 6. *Theorem 6. We can implement a priority queue that with $n$ integer keys in the range $\[0 , N)$ in linear space supporting **ﬁnd-min**, **insert**, and **dec-key** in constant time, and **delete** in $\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$ time for a key of rank $q$.*

### Reference

Thorup, Mikkel. “Integer Priority Queues with Decrease Key in Constant Time and the Single Source Shortest Paths Problem.” In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, 149–158. STOC ’03. New York, NY, USA: ACM, 2003.

# Answer
> 2 votes
Like with anything in CS, there is no "best something". There are always trade offs. But, perhaps this section of Wikipedia's article on Fibonacci heap could help you:

Fibonacci heap: Amortized $\mathcal{O}(\log\ n)$ delete and delete\_min, amortized $\mathcal{O}(1)$ decrease\_key and $\mathcal{O}(1)$ the rest.

Brodal queue: Worst-case $\mathcal{O}(\log\ n)$ delete and delete\_min, $\mathcal{O}(1)$ the rest.

Pairing heap: Amortized $\mathcal{O}(\log\ n)$ delete and delete\_min, unknown decrease\_key, but bounded by $\mathcal{\Omega}(\log \log\ n)$, amortized $2^{\mathcal{O}(\sqrt{\log\log\ n})}$, $\mathcal{O}(1)$ the rest.

# Answer
> 0 votes
Finally a simplification of the Brodal queue\[1\] has been released\[2\], which unlike\[3\]; are worst-case values (rather than amortised).

**Insert**: $\mathcal{O}(1)$

**Find-min**: $\mathcal{O}(1)$

**Decrease**: $\mathcal{O}(1)$

**Meld**: $\mathcal{O}(1)$

**Delete-min**: $\mathcal{O}(log\ n)$, that's equivalent to $\approx 70\ log\ n$ here, which is a smaller constant than Brodal.

---

\[1\] Brodal, Gerth Stølting. “Worst-case Efficient Priority Queues.” In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 52–58. SODA ’96. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1996.

\[2\] Elmasry, Amr, and Jyrki Katajainen. “Worst-Case Optimal Priority Queues via Extended Regular Counters.” In Computer Science – Theory and Applications, edited by EdwardA. Hirsch, Juhani Karhumäki, Arto Lepistö, and Michail Prilutskii, 7353:125–137. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2012.

\[3\] Takaoka, Tadao. “Theory of 2-3 Heaps.” In In Computing and Combinatorics, Volume 1627 of LNCS, 41–50. Springer, 1999.

# Answer
> 0 votes
### Worst-case complexity

$\mathcal{O}(log\ M)$ insert, search, delete \[see 'Lemma 3.1'\]

$\dagger\ \mathcal{O}(1)$ findMin, findMax, extractMin, extractMax, predecessor, successor

$2M + \mathcal{O}(log\ M)$ bits of ordinary memory and $m$ bits of Yggdrasdil memory \[this second type of memory is defined in the paper\]

(where $M$ is the bounded integer universe: $M = \[0, \cdots, M - 1\]$

### Question about my analysis of the paper

$\dagger$ Can someone confirm this result, as I am assuming it from 'Theorem 3.1'; i.e.: that "update" in 'Lemma 3.3' only refers to random inserts and deletes rather than extract{Min,Max}.

---

Brodnik, Andrej, Svante Carlsson, Michael L. Fredman, Johan Karlsson, and J. Ian Munro. “Worst Case Constant Time Priority Queue.” Journal of Systems and Software 78, no. 3 (2005): 249 – 256. doi:10.1016/j.jss.2004.09.002. (I read the 6 page version)

# Answer
> -1 votes
### Worst-case complexity

**$\boldsymbol{\mathcal{O}(1)}$ insertion**

**$\boldsymbol{\mathcal{O}(log\ \textbf{min}\\{w\_x, q\_x\\})}$ get-min, extract-min, delete, and decrease of an element $\boldsymbol{x}$**

Where $w\_x$ (respectively, $q\_x$) is the number of elements that were accessed after (respectively, before) the last access to $x$ and are still in the priority queue at the time when the corresponding operation is performed.

A. Elmasry, A. Farzan, and J. Iacono, “A priority queue with the time-finger property,” J. of Discrete Algorithms, vol. 16, pp. 206–212, Oct. 2012.

---
Tags: data-structures, time-complexity, priority-queues
---


# Question
Title: How Does Dynamic Heap Storage Have Something to Do with Heap?
There are three typical ways to allocate memory for programs: static, stack and dynamic heap. However, when I look at the implementation of dynamic heap memory allocation from wikipedia, what I found is fixed block allocation, etc. So why is dynamic memory allocation called "heap" memory allocation? How does it have something to do with "heap"?

# Answer
> 6 votes
Heap memory and the heap data structure are two different and unrelated things. This really bothered me when I was learning about memory, especially since stack memory was actually a stack. The original use of the word heap in computer science referred to the data structure. However, in the 1970s some authors began to use the word heap to refer to the pool of available memory. This use actually more closely matches the English definition of heap - an untidy collection of things - since heap memory is a messy place to allocate and deallocate memory. The name stuck and now we have multiple meanings for the word heap.

---
Tags: programming-languages, compilers, operating-systems, memory-management, memory-allocation
---


title: DFS - Proof of Correctness

text:
# Question
Title: DFS - Proof of Correctness
I'm currently studying the book "Introduction to Algorithms - Cormen". Although a proof of correctness for the BFS algorithm is given, there isn't one any for the DFS in the book. So I was courious about how it can be shown that DFS visits all the nodes. I also googled for it. But it seems that every lecturer do some copy-paste work from this book in their pdf's, so I couldn't find anything useful.
By DFS we had to show that it found the shortest path. But since DFS does not calculate something like that I have no idea how to prove it.

---

Off the topic, why are those proofs so important? Throughout the book there are so many lemmas and theorems which can be really boring sometimes. I understand how an algorithm works in 10 minutes, perhaps need another 5 to 10 minutes to understand how to analyse the running time, but then I'm loosing 1 hour just for some useless lemmas. Besides, and worse even, I studied almost 50 proofs/lemmas of different algorithms till now, I never managed to solve one of them by myself. How can I gain the "proving ability"? Is there a systematical way to learn that? I don't mean the Hoare logic way with invariants, rather the informal way described in the book "Introduction to Algorithms". Is there any book which focuses on "how to prove algorithms" and show that in a systematical, introductory way ?

# Answer
**From lecture notes by Prof. Danny Sleator:**

Basic DFS algorithm: Each vertex has a binary field called "visited(v)". Here's the algorithm in pseudo-code:

```
 for all v in V do visited(v) = 0
 for all v in V do if (visited(v)==0) DFS(v)

   DFS(v) {
      visited(v) = 1
      for all w in adj(v) do if (visited(w)==0) DFS(w)
   }

```

Claim 1: DFS is called exactly once for each vertex in the graph.

Proof: Clearly `DFS(x)` is called for a vertex `x` only if `visited(x)==0`. The moment it's called, `visited(x)` is set to `1`. Therefore the `DFS(x)` cannot be called more than once for any vertex x. Furthermore, the loop "for all v...DFS(v)" ensures that it will be called for every vertex at least once. QED.

Claim 2: The body of the "for all w" loop is executed exactly once for each edge (v,w) in the graph.

Proof: `DFS(v)` is called exactly once for each vertex v (Claim 1). And the body of the loop is executed once for all the edges out of v. QED.

Therefore the running time of the DFS algorithm is `O(n+m)`.
> 2 votes

# Answer
I had the same problem when I was an undergrad. I can see you understand the algorithm. And, to *prove that it works* is to explain it formally that it works.

Why we have many proofs ? because we may have algorithms that are not correct, and we need to show that our algorithm is correct and actually work *always!*.

Same for the analysis. If we want to prove for example that our algorithm is better than others, then we prove it. You may tell me that we can implement our algorithm and and test it, but this does not consider *all* the possible cases of input. Therefore, what we do is to *prove it*.

(We usually prove the correctness and complexity of an algorithm (which is a measure of its performance)).

This is just an answer for your second question. For your first question, a hint is to say *why* we will visit every other vertex if the graph is connected. \[Hint: because the graph is connected than for every pair of vertices there is a path.\] ...(back to your second question).. if you note here that I am using one fact to prove my original fact (i.e., there is a path connecting every pair of nodes --\> DFS is correct). The first fact is clear in our case given the definition of connectivity. In many other cases, it is not clear. So we will need to prove one fact by proving another, and perhaps do that again and again. This is why we have a lot of lemmas and theorems.

They are boring now. but once you see their magic, you will love them ! As a fun excercise try to solve simple algorithmic problems and prove their correctness and analyses. To verify your answers, re-read your answers. If they convince you, then you are correct. If not, then re-do it again.
> 3 votes

# Answer
AJed puts things very nicely, and ajmartin has provided you with a proof too. I would like to add the following to your second question:

If you *really* understood the algorithm, then you should also understand these properties of the algorithm, and be able to *explain* them to others informally - say to friends or colleagues (such as how and why a shortest path is found). If you don't realize these properties on your own, you should at least realize them once you are told (such as by being asked to prove them). If you can do that, from there it is just a matter of writing down things formally (which can be achieved with practice). If you can't explain that, or don't understand things like why it visits every node, then you have not *really* understood the algorithm - just understood how to implement it.

I know proofs are often written in a more complicated manner than necessary. And can be difficult to understand easily. But that should not undermine the importance of proofs - it just shows proofs should be as simple as possible without being ambiguous/loose/incorrect.

Proofs make things water-tight. It allows the algorithm to form the basis of more complex analysis/algorithms/theories without having to be re-assessed. You need to show that the algorithm is correct for *all* inputs that it claims to handle. Just intuition may not always be sufficient (or sometimes may also be misleading). You say that in software development, there are ways to test things for most cases. But if the algorithm is proven correct, all you need to check is that the algorithm has been implemented correctly.

Put another way, what if someday you come up with a brilliant algorithm for some problem in your work. The algorithm is complex and no-one understands it. How do you convince others that the algorithm works, and that they could use it too? Equally (or more?) importantly, how would you convince your boss that your brilliant idea actually works and won't cause cataclysmic failures for some cases which have not been tested - especially since no one else has used the algorithm before? The answer is you prove the correctness of your algorithm, and show that it has been correctly implemented. You need proof techniques for that, and so are taught these in university - unlike your claim in your comment as posted as answer - it is not something only useful for masters or phd.

A side-effect of proofs is that they often offer deeper insight into the algorithm. Taking the very trivial case of your question, if you read a proof of why every edge and vertex is visited exactly once, or why and how it finds a shortest path, you will be able to better understand and visualize the working of the algorithm.

As for why there are so many lemmas, it is the same thing as programming. You could write the whole block of proof at once (as you could write the whole code in one chunk), but that would be unwieldy, tough to understand and error-prone. If, however, you write modular code, it becomes easy to re-use the modules (functions/classes), easier to test, verify, understand and abstract out complications. The same is true for proofs. You break it down into simpler "modules" - they are just called lemmas/claims etc. You get more or less the same benefits from lemmas that you get from modular code.
> 2 votes

---
Tags: algorithms, graphs, correctness-proof
---


# Question
Title: Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?
I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem.

> **Halting function:** The Halt function takes an input a pair $\<\alpha, x\>$ and outputs 1 if and only if the TM $M\_{\alpha}$ represented by $\alpha$ halts on input $x$ within a finite number of steps.

The undecidability of Halting function is proved by reduction from another undecidable function $UC$, which is defined as follows Book by Arora and Barak.

> **$UC$:** For every $\alpha \in \lbrace 0,1 \rbrace^{\ast}$, if $M\_{\alpha}(\alpha) = 1$, then $UC(\alpha) = 0$; otherwise (if $M\_{\alpha}(\alpha)$ outputs a different value or enters an infinite loop), $UC(\alpha) = 1$.

The undecidability of $UC$ is proved by the also well-known *"diagonalization"* technique. I can understand the technique. However, I am puzzling over a more basic problem involving the definition of $UC$.

> **My Problem:** The definition of $UC$ is based on the value of $M\_{\alpha}(\alpha)$. Especially, it seem to be based on *whether a Turing Machine halts on an input*. However, the latter is undecidable (Worse still, it is undecidable due to the undecidability of $UC$!). In this sense, is the $UC$ function well-defined?

What is wrong with my opinion? How should I understand the definition of $UC$ and the relation between $UC$ and Halting Problem?

Thank for your help.

# Answer
> 7 votes
In classical logic it is possible to define a function which is not computable, and $UC$ is such a function. What probably confuses you is that you think that a function must always be given in a symbolic form, or as a set of instructions on how to compute it, or some such. But this is not necessary. Officially a function $f : A \to B$ is the same thing as a subset $F \subseteq A \times B$ satisfying the *functionality condition*:

> For every $x \in A$ there is exactly one $y \in B$ such that $(x,y) \in F$.

We may apply this to our situation to define $UC$ as the set of pairs $$UC = \lbrace ((\alpha, x), d) \mid (\text{$M\_\alpha$ halts on $x$ and $d = 1$}) \lor (\text{$M\_\alpha$ does not halt on $x$ and $d = 0$}) \rbrace.$$ Even though nobody told us how to discover the output $d$ for a given input $(a, x)$, it is still the case that for every $(a,x)$ there is exactly one $d$. Indeed, if there were more than one then we would have a machine $M\_\alpha$ which both halts and does not halt on input $x$. And if there were no such $d$, that would mean we have a machine $M\_\alpha$ which neither halts nor not halts on input $x$.

In constructive logic one cannot define a non-computable function. And neither can one show that all functions are computable. So there $UC$ would not satisfy the functionality condition, and it would only define a *partial* function. But we could still talk about the fact that the Hlating problem is not decidable because the same classical argument still applies (we just avoid talking about $UC$). Assume there is a Turing machine $H$ such that:

1. $H$ halts on every input.
2. If $M\_\alpha$ halts on $x$ then $H$ on input $(\alpha, x)$ outputs $1$.
3. If $M\_\alpha$ does not halt on $x$ then $H$ on input $(\alpha, x)$ outputs $0$.

We now proceed with the usual diagonalization argument and construct a machine $B$ with a code $\beta$ such that $B(\beta)$ halts if, and only if, $H(\beta, \beta)$ outputs $0$. Everything here is perfectly constructive. I only took care never to assume that every machine either halts or not (such an assumption is implicit in the definition of $UC$).

So perhaps you should stick to constructive mathematics, and there will be fewer surprises for you.

# Answer
> 5 votes
The function $UC$ is well-defined. Of course, the definition is not given by some sort of algorithm but by a formal statement. In particular, the value of $UC(\alpha)$ can be either 1, if some condition $X$ is satisfied, or 0 if condition $Y$ is satisfied. But since $X$ ($M\_\alpha(\alpha)=1$) is the negation of $Y$ ($M\_\alpha(\alpha)\neq 1$) the definition is well-defined. It would **not** be well-defined if $X$ and $Y$ could both hold, or none of $X$ and $Y$ could hold.

Notice that a definition of a function can be expressed by an algorithm, but this is not necessarily the case. Other not-computable functions with a short definition are $$\begin{align} \text{BB}(\alpha)&:=\text{maximal number of cells a halting Turing machine with $\alpha$ states can print},\\ \text{KOL}(\alpha)&:=\text{minimal size of a Turing machine program that prints $\alpha$ and stops}. \end{align}$$

(These are the busy-beaver function and Kolmogorov complexity.)

---
Tags: computability, proof-techniques, undecidability, halting-problem
---


title: Decision problem and algorithm

text:
# Question
Title: Decision problem and algorithm
I was reading about decision problem. I understand that decision problem tell yes/no answer for an input. The decision is based on a decision procedure also called an algorithm.

The wikipedia says that

> It is traditional to define the decision problem equivalently as: the set of inputs for which the problem returns yes.
>
> These inputs can be natural numbers, but may also be values of some other kind, such as strings over the binary alphabet $\\{0,1\\}$ or over some other finite set of symbols. The subset of strings for which the problem returns "yes" is a formal language, and often decision problems are defined in this way as formal languages.

Whether I can take it like algorithm written in a programming language defines the set of all possibilities and gives the output based on the input?

So in computability theory, the problem should be encoded to some form? Is this same thing as the input tape and configuration of a Turing machine (set of 0's and 1's )?

# Answer
Traditionally, in computability theory all problems are encoded in terms of numbers, or sometimes strings of bits $0$ and $1$. This is a very "low level" kind of thing, it is like programming directly in machine code. The reason for doing this is mostly historic. Gödel originally encode first-order logic in terms of numbers to prove his incompleteness theorems. Similarly, if one approaches computability through recursive functions, it is natural to encode everything with numbers. And mathematicians just like numbers anyway.

A computer scientist would recognize the benefits of using a more advanced programming language that supports datatypes. Programmers know that programming in machine code obscures a lot of ideas and makes everything technically difficult. Mathematicians know this too, but since they do not actually write code, just think about writing code, they do not appreciate this point of view sufficiently to switch from their traditional ways.

So, to answer your question, here is a modern way of defining decision problems. Pick your favorite general-purpose programming language. Consider a datatype $D$ (can be numbers, lists, heaps, trees, whatever) and decompose the values into two disjoint sets $D\_0$ and $D\_1$, so that $D\_0 \cap D\_1 = \emptyset$ and $D\_0 \cup D\_1 = D$. Observe that $D\_1$ uniquely determines $D\_0$ and vice versa, because $D\_0 = D \setminus D\_1$. So we only have to specify $D\_1$.

Now, a decision problem $(D\_0, D\_1)$ is said to be *decidable* if there is a program $p : D \to \mathtt{bool}$ such that:

1. $p$ is *total*, which means that $p(d)$ halts for every $d \in D$,
2. if $d \in D\_0$ then $p(d) = \mathtt{false}$,
3. if $d \in D\_1$ then $p(d) = \mathtt{true}$.

All that stuff about encodings and finite words over an alphabet etc. is not necessary. It is only useful if you want to prove general theorems about arbitrary decision problems. But if you want to think about a specific decision problem, it is better to do it directly in your favorite programming language.
> 11 votes

---
Tags: computability, turing-machines, undecidability, decision-problem
---


title: How is a star topology a regular graph?

text:
# Question
Title: How is a star topology a regular graph?
A regular graph is one in which each vertex has the same number of neighbors, but in a star topology the central vertex is connected to more than one vertex. So, why is it referred to as a regular graph?

# Answer
summarizing the comments: by the standard definition, a star is not a regular graph.

They might defined "regular" in a different way than common to apply to star topology. Specifically, in the paper the OP point out "regular" is never defined (and sparsely used).
> 3 votes

---
Tags: graphs
---


title: Time Complexity of Genetic Algorithms

text:
# Question
Title: Time Complexity of Genetic Algorithms
How do you determine the Time Complexity of a Genetic Algorithm(in general)? If possible.

I have been thinking about this a lot, and all of the teaching I have had is related to determining the Time Complexity of problems that are much less stochastic in nature.

# Answer
> 9 votes
Genetic algorithms are a metaheuristic and as such there is no general analysis that applies to all genetic algorithms at once (without being super loose). In general, when you are searching for information on the run-time of genetic algorithms, you will have more luck if you use the terms "convergence time", since that is the more common terminology. A good start on some formal techniques:

Y. Rabinovich, A. Wigderson. Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999.

For more resources on formal treatments, consider the cstheory question: Provable statements about genetic algorithms.

# Answer
> 4 votes
I agree with the previous answers, and I also add the following.

We usually dont care about the time complexity of a genetic algorithm. We usually care how good are the results in comparison to some benchmark, and about the convergence rate.

You can see however that genetic algorithms runs in iterations. Initially, a set of solutions $S$ are generated randomly ($S$ is called a population). The costs of the solutions of $S$ are computed. Some operations are done over the the solutions of $S$ in each iterations such as crossover, mutation etc ... . The best $k$ solutions in $k$ are kept in $S$ and we continue as previous. After the last iteration, we output the best solution we found.

You can note here that the time cost of an iteration depends on the inner operations (e.g. crossovers, mutation and others, finding best $k$ distinct solutions, generate random solutions, calculate cost of the solutions of $S$ etc .. ) which are usually simple to implement, and also problem-dependent. In general, they depend on the size of a solution.

The execution time of a genetic algorithm also depends on the number of iterations (obviously !). Typically, we want to stop when we *converge* to a solution that is hardly improved. How to find the number of iterations that guarantee this ? there are some probabilistic analyses to find the average convergence time. See for example \[1\] (quite interesting results). But you will note that we did not reach yet the level of analyzing the complex problems where genetic algorithms are used. Therefore, in many cases, the number of iterations in a genetic algorithm is decided experimentally.

\[1\] Oliveto, Pietro S., Jun He, and Xin Yao. "Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results." International Journal of Automation and Computing 4.3 (2007): 281-293.

---
Tags: time-complexity, evolutionary-computing
---


# Question
Title: Type inference in compiler is context sensitive?
Have read in Compiler textbook that type inference is context sensitive. Can anyone explain why is it so? This means that we need context sensitive grammar in semantic analysis phase of a compiler with this feature? How is it done in popular programming languages like C?

# Answer
The context that is needed tells us the types of known variables. Suppose We want to infer the type of

```
if b or 2 = x then a else b

```

To make sense of this we need to

1. Check that the type of `b` is `bool`
2. That the type of `x` is numeric
3. That `a` and `b` have the same type.

To answer these three questions, we look up information about variables in a *typing context*, which is a mapping from variables to their types. Furthermore, the result is context-sensitive, as the type of the whole expression is the type of `a` (and `b`), which is given by the information in the context.

Now you are also mentioning grammars. These are not really relevant here, because we are talking about a stage of compilation which comes after parsing. I think you just got confused by the word "context" being used outside of the subject of grammars. Or you are reading a very strange book. By the way, there is a reason scientists want other scientists to give precise references to their sources. So instead of saying "I read a compiler book", you should have given the author and the title. Now I am just guessing.
> 6 votes

---
Tags: formal-languages, programming-languages, context-free, compilers, context-sensitive
---


# Question
Title: Data structure with search, insert and delete in amortised time $O(1)$?
Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?

* **GetElement(k)**: Return the $k$th element of the list.
* **InsertAfter(x,y)**: Insert the new element y into the list immediately after x.
* **Delete(x)**: Remove x from the list.

For the last two operations, you can assume that x is given as a pointer directly into the data structure; InsertElement returns the corresponding pointer for y. InsertAfter(NULL, y) inserts y at the beginning of the list.

For example, starting with an empty data structure, the following operations update the ordered list as shown below:

* InsertAfter(NULL, a) $\implies$ \[a\]
* InsertAfter(NULL, b) $\implies$ \[b, a\]
* InsertAfter(b, c) $\implies$ \[b, c, a\]
* InsertAfter(a, d) $\implies$ \[b, c, a, d\]
* Delete(c) $\implies$ \[b, a, d\]

After these five updates, GetElement(2) should return d, and GetElement(3) should return an error.

# Answer
> 7 votes
Looks like the $\Omega(\dfrac{\log n}{\log\log n})$ barrier has been overcome by modifying the analysis from the chronogram technique.

The new \[lower\] $\Omega(\log n)$ bound has been proved for similar problems in the cell-probe model \[1\]. From reading that article; it is my understanding that that bound applies to the *list representation* problem also.

---

\[1\] Patrascu, Mihai, and Erik D. Demaine. “Logarithmic Lower Bounds in the Cell-Probe Model.” SIAM J. Comput. 35, no. 4 (April 2006): 932–963. doi:10.1137/S0097539705447256.

# Answer
> 36 votes
**NO.**

Fredman and Saks proved that *any* data structure that supports these operations requires at least $\Omega(\log n/\log\log n)$ amortized time per operation. (This is reference \[1\] in the paper by Dietz that you mention in your first comment.) The lower bound holds in the *very* powerful cell probe model of computation, which only considers the number of distinct memory addresses accessed by the update and query algorithms.

Without some additional assumptions about the update and query operations, Dietz's data structure is the best possible (at least up to constant factors).

---
Tags: data-structures, time-complexity, asymptotics, amortized-analysis
---


# Question
Title: Can terms "interpreter" and "processor" be used interchangably?
I do not ask you to respect that the processor is a physical black box whereas interpreter implementation is not that clear. As CS, you must look at the functionality aspect -- both processor (physical machine?) and interpreter (virtual machine?) execute a program (a stream of commands).

Isn't *to interpret* the code just means *to evaluate/to execute/to process* it?

There is a long article on interpretation in Wikipedia. It uses a lot of words to explain what is interpretation and it even says that it is execution of instruction stream. But nobody stood up and stated that it is just what the processor does (like the child in the "Emperor new clothes")! Why should we think that these are two different things? Processors even invented JIT-compilation (called microcoding) earlier than virtual machines.

Also, bytecode interpretation should give additional clue. It looks like machine code absolutely (to be executed by virtual machines). So, are interpreters just virtual processors?

The self-checking questions are:

1. What if vendor of your favorite processor discloses you a terrible secret that your instructions are not executed directly but converted into a true machine language beneath, before submitted to the real processor, is you language interpreted or machine?
2. What if instruction stream for a real processor is executed by emulator (virtual machine) then is it executed by the processor or interpreted?
3. Can the processor that executes an interpreted language (bytecode or script) is not a processor anymore but an interpreter?

# Answer
> 4 votes
Usually, an interpreter is defined in computing terms: it executes instructions by issuing instructions to some lower level of processing. A processor is defined in physical terms: it executes instructions in electronic circuits. It's an interpreter if its behavior is ultimately defined by computer scientists, and a processor if its behavior is ultimately defined by physicists.

There's an exception: if the interpreter is defined in terms of emulating something that would normally be a physical processor, it's called a processor.

But it's only a matter of terminology. There's no profound distinction here. Just go with the flow.

1. Mu. It's an interpreted machine language. Many processors work that way anyway (where do you draw the line between instruction decoding and interpretation? why would you want to draw a line?).
2. Mu. It's a processor, and the processor is interpreted.
3. Mu. If you posit that the language is interpreted then by definition it's interpreted by an interpreter. The interpreter may be a processor.

# Answer
> 1 votes
No. Inside my Mac there is a processor, not an interpreter. ZX Spectrum came with a Basic interpreter built in, not a Basic processor.

What is the point of this question?

---
Tags: terminology
---


# Question
Title: Is there a simple example of sets such that $A \leq_T B$ but not $A \leq_m B$?
I wonder if there is a simple example of sets $A$ and $B$ such that $A$ is Turing-reductible to $B$ but not many-to-one reductible to $B$.

# Answer
> 11 votes
For example sets $H = \\{x \\, | $ Turing machine with index $x$ halts on input $x\\}$ and $\overline{H} = \\{x \\, | $ Turing machine with index $x$ doesn't halt on input $x\\}$.

Because if $\overline{H} \leq\_m H$, then $\overline{H}$ would be recursively enumerable and therefore $H$ would be recursive, which is contradiction.

On the other hand $\overline{H} \leq\_T H$, because there is Turing machine with oracle $H$ recognizing $\overline{H}$. This machine for input $x$ just checks $x \in H$ and negates the answer.

# Answer
> 0 votes
The key distinction (or at least one important one) is that Turing reductions are *oracle* based, whereas many-one reductions require a *total computable function* (i.e. you need to be able to map all inputs to something). With this in mind we can get a pretty clear example:

Consider the set of Turing machines that halt on some fixed input (for argument's sake, empty input is good enough), and the set that don't halt on the same fixed input. It should be clear these are Turing equivalent (if we have an oracle for one, we can use it to answer the other - just run the oracle on the input and give the opposite answer).

On the other hand, if we had a computable function that converted machines that don't halt into ones that do and vice versa, we'd be able to decide the halting problem.

# Answer
> 0 votes
Let $A$ be any nontrivial language such as $\\{a\\}$ and let $B$ be the empty language $\emptyset$.

$A$ is Turing-reducible to $B$ because, given an oracle for the empty language, we can determine if an input string is $a$ or not. (We need not even use the oracle.)

But $A$ is not many-one reducible to $B$ because there is nothing to map the input $a$ to.

---
Tags: turing-machines, reductions
---


# Question
Title: Good explanatory resource for algorithm techniques such as greedy, backtracking and recursive functions
What would be a good book/resource that explains the basic idea behind those techniques, how to use (and maybe when to use them) and plenty of exercises with perhaps some worked examples (kind of like when for loops were introduced for the first time you were asked to use one to compute sums of odd numbers, even numbers etc.) ?

If the explanation is both formal and "plain" (for dummies style explanation) that would be great. Thanks!

# Answer
The Coursera course on Algorithms running currently suggests four books:

* CLRS - Cormen, Leiserson, Rivest, and Stein, Introdution to Algorithms (3rd edition)
* DPV - Dasgupta, Papadimitriou, and Vazirani, Algorithms
* KT - Kleinberg and Tardos, Algorithm Design
* SW - Sedgewick and Wayne, Algorithms (4th edition)

Sedgewick and Wayne is apparently very implementation-oriented, with tons of Java examples as well as testing metrics and lots of models. I haven't checked it out myself, but I will be.

Another great book is the Algorithms Design Manual by Skiena, apparently also very programmer-friendly.
> 2 votes

# Answer
I think it's hard to beat the CLRS book (Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein) in terms of depth, breadth, or clarity of explanation. Algorithm Design, by Kleinberg and Tardos, is also very good and not nearly as intimidating.

Personally, even as someone who enjoys learning out of books most, starting from scratch with an algorithms textbook seems like a rough introduction to the subject. I think it would be easier if you watched video lectures, as there are some very high-quality lectures available on the internet nowadays. In general I'd encourage you to search MIT opencourseware and other similar offerings. This class might be a good option that I've used to brush up on some basic stuff earlier this year (scroll down to "Videos"). Unfortunately the videos there are considerably low-quality; you may be better off finding another class. Youtube EDU also has some filmed lectures that may be useful, particularly if there are some specific topics you're interested in.
> 2 votes

# Answer
For recursion have a look at this tutorial:

It follows somehow the "dummies" way but it is very illustrative and relatively strong (I mean you will get the necessities). The main problems is that you will have to learn a new paradaigm of programming \[if you dont know it already\] (the functional languages paradaigm). But these are the best to study recursion.

(if you find something like this about other algorithm techniques, please let me know. This would be beneficial for a lot of high school students interested in CS).
> 1 votes

---
Tags: algorithms
---


# Question
Title: Neural Network weight selection using Genetic Algorithm
Hi I want to ask about weight selection in neural network using genetic algorithm.

Right now what I understand is

1. Initialize population
2. Encode the weight of the neural network to the chromosome
3. Calculating the error and fitness
4. crossover and mutation
5. looping until satisfy the condition

Is it the right thing?

if yes what I'm still not sure are :

1. If I have 50 chromosome in one population that means I must create 50 neural network?
2. Let's say I have 100 different input and I want the network to learn it by using weight selection only (not using backpropagation) and how I calculate the error? Testing and calculating the error of every input(using MSE) and divide it by 100?

I think that's all for now

Thank you

# Answer
Your understanding is correct.

1. Yes, you do create a new neural network for each chromosome (although you're considering the network structure as fixed, so technically you could reuse them by just resetting the weights anew for each chromosome.
2. For the error, you're on the right track. For a GA, generally only relative differences in fitness are important, so it doesn't really matter if you divide by 100 or not -- that's just linearly scaling the fitness values. That *might* matter for some choices of genetic operators (e.g., roulette-wheel selection can be sensitive to absolute fitness values), but often it won't matter at all.
> 2 votes

---
Tags: neural-networks
---


title: Graph Bipartiteness

text:
# Question
Title: Graph Bipartiteness
I have 2 questions regarding Bipartiteness with corresponding examples.

1) Can a non-connected graph be bipartite if it has an isolated vertex? Let's take the following graph:
I would say YES with this partition: V1 = {A, D, G} ; V2 = {B, C, E, F, H}
But what confuses me is that A is isolated.
Is that a contradiction to the bipartitiness of G ?

2) Is there a rule about the uniqueness of the partitions ? Let's take the following graph:
choice1: V1= {A, C}; V2 = {B, D}
choice2: V1= {A, D}; V2 = {B, C}

Does it matter which one i choose?

# Answer
A graph with two sides L and R such that all edges go between L and R is a bipartite graph.

Hence, your first part is correct and so is your second part. It doesn't matter as long as both are independent sets.
> 3 votes

---
Tags: graphs, bipartite-matching
---


title: Prove or refute: BPP(0.90,0.95) = BPP

text:
# Question
Title: Prove or refute: BPP(0.90,0.95) = BPP
I'd really like your help with the proving or refuting the following claim: $BPP(0.90,0.95)=BPP$. In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most $\frac{1}{3}$ for all instances. $BPP=BPP(\frac{1}{3},\frac{2}{3})$.

It is not immediate that any of the sets are subset of the other, since if the probability for an error is smaller than $0.9$ it doesn't have to be smaller than $\frac{1}{3}$ and if it is bigger than $\frac{2}{3}$ it doesn't have to be bigger than $0.905$.

I'm trying to use Chernoff's inequality for proving the claim, I'm not sure exactly how. I'd really like your help. Is there a general claim regarding these relations that I can use?

# Answer
> 13 votes
To expand out my comment into an answer: the multiplicative form of Chernoff's bound says that if the expectation $X=\sum\_{i=0}^n X\_i$ for the sum of independent random binary variables is $\mu$, then the probability of straying 'too far' from that expectation goes as: $Pr(X\gt (1+\delta)\mu) \lt \left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu$.

Now, imagine a procedure where, given a string $\sigma$ to test, we run $n$ trials of our $BPP(0.90, 0.95)$ algorithm (for some $n$ to be chosen later) and accept iff at least $0.925n$ of those trials accept $\sigma$. We can use Chernoff's bound to find the probability of failure in terms of $n$ as follows:

Let $X\_i$ denote the outcome of the $i$th trial, and thus $X=\sum X\_i$ the number of trials that succeed. We can assume conservatively that our probability for false positives is $.9$; this means that if we make $n$ independent trials on a string $\sigma\notin L$, the expected number of successes is $\mu = E(X) = 0.9n$. (Note that a false positive probability less than $.9$ will lead to an even lower expected value and thus to even tighter bounds on the estimates to come.) Now, let's look at the probability that we have more than $0.925n$ false positives (i.e., that $X\gt 0.925n$). We take $\delta = \left(\frac{0.925}{0.9}\right)-1 =\frac{1}{36}$; then $\left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right) \approx.99961\lt \frac{2999}{3000}$ and so we have $Pr(X\gt 0.925n)\lt\left(\frac{2999}{3000}\right)^{0.9n}$.

From here it should be clear that by taking $n$ large enough we can reduce this probability to $\lt\frac{1}{3}$. Thus, for this sufficiently large $n$, if we accept the string $\sigma$ only if the number of successful trials on $\sigma$ is greater than $.925n$, then our probability of accepting a string $\sigma\notin L$ drops below $\frac{1}{3}$. Note that this $n$ is *constant*, not dependent on our problem size; since we're running our polynomial $BPP(0.9, 0.95)$ algorithm a constant number of times, the total running time of our new procedure is still polynomial. A similar analysis going the other direction will show that the probability of a 'false negative' (that $X\lt.925n$ for a string that is in our language) will be bounded by $c^n$ for some $c$, and so again we can take $n$ large enough to bound the probability of a false negative by $\frac{1}{3}$ (or, in other words, to ensure at least $\frac{2}{3}$ probability of accepting on a string $\sigma\in L$). This shows that $BPP(.9, .95)\subseteq BPP(\frac13, \frac23) \equiv BPP$, and Yuval's comment shows how to prove the reverse equivalence through a similar procedure.

Canonically, this is known as *probability amplification* and it's an immensely useful method for dealing with probabilistic classes. The specific constants are less important, obviously, then the fact that Chernoff's bound lets us bound our 'false result' probabilities by some exponential function of the number of trials, so they can be made arbitrarily small with only a modest number of trials.

---
Tags: complexity-theory, time-complexity, probabilistic-algorithms
---


# Question
Title: Proving that the clique cover problem is in NPC by reducing from k-coloring
Provided that we have to compare it against the graph coloring problem which is NPC. So far, I can only think of connecting edges from a vertex in a provided graph to all the other edges it is not connected to then I separate the new graph g2, then I connect all the vertices that are not connected in the g2. And then I count the number of subsets. However it doesnt seem to work with a graph that requires four colors?

# Answer
> 2 votes
In the interests of putting up an explicit answer, your approach is correct. The proof is sketched on the Wikipedia page for Clique Cover.

The reduction itself is fairly straightforward. The reasoning is that if a graph is $k$-colourable, then it can be partitioned into $k$ independent sets (one for each colour class), then we just exploit the normal reduction between Independent Set and Clique by taking the complement graph (we swap edges for non-edges and vice versa), so any independent set becomes a clique. So if $G$ is $k$-colourable, it can be partitioned into $k$ independent sets and hence $\overline{G}$ can be partitioned into (i.e. covered by) $k$ cliques (but not necessarily by $k$-cliques ;) ). Conversely if $\overline{G}$ can be covered by $k$ cliques, $G$ has a partition into $k$ independent sets, and hence is $k$-colourable.

---
Tags: graphs, np-complete, reductions
---


title: Maximum weight matching

text:
# Question
Title: Maximum weight matching
There are polynomial time algorithms to find maximum weighted matching in a general graph. Is there any algorithm that also handles negative weights in the general graph and find maximum weighted matching for that graph with negative weights ?

# Answer
> 3 votes
I was only familiar with the Hungarian algorithm which only works for bipartite graphs but I've found something that claims to work for general graphs as well. The basic algorithm is the blossom algorithm, but since you need to find the maximum weight matching you will need Kolmogrov's Blossom V which is based on it.

# Answer
> 0 votes
Min cost flow finds the minimum weight of the maximum flow in the network. Use {0,1} capacities to turn it to matching. It can be modified for maximum weight.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow1
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow2
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow3

---
Tags: algorithms, graphs, matching
---


# Question
Title: Smoothing frequencies without count data
I have frequency data for different events under two conditions, resulting in sets of frequencies F1 and F2. I would like to normalize the frequencies of events under condition 1 by their frequencies under condition 2. However, there are events that occur in condition 1 but not condition 2, resulting in divide-by-zero problems when I attempt to normalize.

For raw count data, I understand that there are a number of smoothing techniques (e.g. Witten-Bell) that can help sort this out, but I only have the frequencies, not the individual counts. In other words, I have frequencies like {0, 0.1, 0.2, 0.7} which could correspond to counts of {0, 1, 2, 7}, {0, 10, 20, 70}, etc. Are there any algorithms that are able to smooth this type of frequency data?

# Answer
Yes. $\\:$ Assume that the counts have the smallest sum that would produce your frequency data. $\\:$ (How to do that depends on whether the frequencies were calculated and stored as doubles or something else.)
> 0 votes

---
Tags: algorithms, probability-theory
---


# Question
Title: Fixpoints of a transformation of an extended WHILE program
I am doing some excercises to train myself in computability. There is one that I am not able to solve, here it is.

Consider the following transformation associated to an extended WHILE program:

For all $x \in \mathbb{N}$, $\begin{cases} A f(x) = x \cdot f((x+3)/2) & \text{if \\(x\\) is odd} \\ A f(x) = f(x+1) & \text{otherwise} \\ \end{cases}$

1. How many fixed points does $A$ have?
2. Is there a maximum fixed point?
3. Find the minimum fixed point.

I know that a fixed point is a function $f$ such as $A f = f$.

I would say there is an infinite fixed point. But how to prove it?

To calculate the minimum, I would make a table with on each row: $\bot$, $A \bot$, $A^2 \bot$, ... and if there are two similar lines, that's our minimum. But once again I am not sure this is enough to do this.

# Answer
> 3 votes
Suppose $f$ is a fixpoint of $A$. First, $$ f(0) = f(1) = f(2) = f(3) = 3f(3), $$ and so $f(0) = f(1) = f(2) = f(3) = 0$. Second, $$ f(5) = 5f(4) = 5f(5), $$ and so $f(4) = f(5) = 0$. Third, if $n = 4m+3 \geq 7$ then $$f(n) = n f(2m+3),$$ while if $n = 4m+1 \geq 9$ then $$f(n) = n f(2m+2) = nf(2m+3).$$ In both cases, $2m+3 \< n$, and so you can prove by induction that $f(n) = 0$ for all odd $n$. That implies that $f(n) = 0$ also for all even $n$, and we conclude that $f(n) = 0$ for all $n$.

Edit: This is the maximal fixpoint. The minimal fixpoint is $\bot$. There are two other fixpoints: $f(n) = 0$ for $n \leq 3$ and undefined otherwise, and $f(n) = 0$ for $n \> 3$ and undefined otherwise.

---
Tags: computability
---


# Question
Title: How to rank search results of short string lists
I have a tree of foods, which I'd like to search to find relevant nodes. What's the best way to rank the results?

Here's an example sub-set after a search for "apple":

```
|-- apple pie
|-+ apples
| |-- cooking
| |-+ eating
|   |-- average
|   |-- Granny Smith
|   |-- Golden Delicious
|-- pork and apple casserole

```

Currently, I'm ranking based on which results come earliest in the full name of each leaf, so a result set would look like:

```
0 Apple pie
0 Apples, cooking
0 Apples, eating, average
0 Apples, eating, Granny Smith
0 Apples, eating, Golden Delicious
2 Pork and apple casserole

```

Where the rank is the index of the first token match, lower the rank the better.

I'd like to aggregate the matches, so that I don't display the full sub-tree on the initial search, for example:

```
Apples... (4)
Apple pie
Pork and apple casserole

```

The obvious way to rank these is to count the number of matching leaves, then the higher the rank, the better the match.

But, I'm not sure how to combine these rankings, since one is larger-is-better and one is smaller-is-better. Are there standard ways to combine rankings like this? (I'm not sure what to search for, so Google is giving me results about search engine optimisation, and searching web pages, which doesn't seem to apply.)

# Answer
Although i dont really know how a result is better. I guess what you are doing is fine (And perhaps the best possibly you can get). Just one note to be more precise, you should be ranking a node $u$ based on the size of the subtree rooted at $u$ (not on the number of leaves in that subtree, or children of $u$). This is better (and more general).

But one way to solve issues like this in general is to give score to each node in your tree (a weight). The higher the score, the more it will be ranked above. Then, you will be looking for the subtree with highest weights. You compute this by summing the weights of all nodes in a subtree.

Example of weights (just to help you a bet):

* closeness to search term (use hamming distance for example, or other metrics \[e.g. look how spelling suggestion algorithms work.\]
* If this is a website of recipes for example, the nodes may be recipes and the weight of a node is how many "likes" it received from the website.

In conclusion, I guess what you are doing is the best approximation to have. Adding the weights is a heuristic to give you perhaps better results.
> 1 votes

---
Tags: search-algorithms
---


# Question
Title: Normalizing the mantissa in floating point representation
How to represent $0.148 * 2^{14}$ in normalized floating point arithmetic with the format

```
1 - Sign bit
7 - Exponent in Excess-64 form
8 - Mantissa

```

$(0.148)\_{10} = (0.00100101\\;111...)\_2$

We shift it 3 bits to left to make it normalized $(1.00101\\;111)\_2 * 2^{11}$.

Exponent = $11+64 = (75)\_{10} = (1001011)\_2$ and Mantissa = $(01001\\;111)\_2$.

So floating point representation is $(0\\;1001011\\;00101111)\_2 = (4B2F)\_{16}$ **Representation A**

But if we store the denormalized mantissa into 8 bit register, then it won't have stored the last three $1$s and then the mantissa would have normalized from $(0.00100101)\_2$ to $(1.00101\\;000)\_2$ by inserting 3 $0$s instead of $1$s.

The representation would have been $(0\\;1001011\\;00101000)\_2 = (4B28)\_{16}$ **Representation B**

So while normalizing, does the processor takes into account the denormalized mantissa bits beyond 8 bits too? Or just rounds it off? Which one is correct: **A** or **B**?

Does it store the mantissa in fixed point representation? How does it all work?

# Answer
> 1 votes
The correct binary representation of $0.145$ is $0.00100101000111...$

Normalized: $1.00101000111...$

The 8 bit mantissa is $00101000 = 0\mbox{x}28$

---
Tags: binary-arithmetic, floating-point, rounding
---


# Question
Title: Algorithm for finding the longest common subsequence using hash table. Why is it slow?
I've designed an algorithm to find the longest common subsequence. The steps are:

Start with `i = 0`

1. Picks the first letter from the first string start from $i^{th}$ letter.
2. Go to the second string looking for that picked letter.
3. If not found return to the first string and picks the next letter and repeat 1 to 3 until it finds a letter that is in the second string.
4. Now that found a common letter in the second string, adds that to `common_subsequence`.
5. Store its position in `index`.
6. Picks next letter from the first string and do step 2 but this time starts from `index`.
7. Repeat 3 to 6 until reached end of string 1 or string 2.
8. If length `common_subsequence` is greater than length of common subsequence so far add that change `lcs` to the `common_subsequence`.
9. Add 1 to the `i` and repeat 1 to 9 while `i` is less than the length of the first string.

> Example
>
> ```
> X = ABCBDAB
> Y = BDCABA
>
> ```
> 1. First pick `A`.
> 2. Look for `A` in `Y`.
> 3. Now that found `A` add that to the `common_subsequence`.
> 4. Then pick `B` from `X`.
> 5. Look for `B` in `Y` but this time start searching from `A`.
> 6. Now pick `C`. It isn't there in string 2, so pick the next letter in `X` that is `B`.

The complexity of this algorithm is $\Theta(n\cdot m)$.

I implemented it using two methods. Here are my implementations.

* First

```
import time
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if string is empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        start = 0 # start position in ystr
        for item in xstr[i:]:
            index = ystr.find(item, start) # position at the common letter
            if index != -1: # if common letter has found
                cs += item # add common letter to the cs
                start = index + 1
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs)
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

```
* Second Algorithm using hash table

```
import time
from collections import defaultdict
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if strings are empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    location = defaultdict(list) # keeps track of items in the ystr
    i = 0
    for k in ystr:
        location[k].append(i)
        i += 1
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        index = -1
        reached_index = defaultdict(int)
        for item in xstr[i:]:
            for new_index in location[item][reached_index[item]:]:
                reached_index[item] += 1
                if index < new_index:
                    cs += item # add item to the cs
                    index = new_index
                    break
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs)
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

```

The second one uses a hash table, but after implementing I found that it's much slower compared to the first algorithm. Can someone elaborate why?

# Answer
One optimization is to replace the access to `reached_index[item]` by a local variable which is initialized from the hash table at the beginning of the `for item` loop, and stored back to the hash table at the end of the loop.

Another optimization which will speed up things is to replace the hash tables with arrays of size 256.
> 1 votes

---
Tags: algorithms, hash-tables, python, subsequences
---


title: sum of like indices in circular lists

text:
# Question
Title: sum of like indices in circular lists
Consider the following problem:

> Let a *$k$-wheel* be defined as an indexed circularly linked list of $k$ integers. For example…
>
> > {3, 4, 9, -1, 6}
>
> …is a 5-wheel with 3 at position 0, 4 at position 1, and so on. A wheel supports the operation of rotation, so that a one-step rotation would turn the above wheel into…
>
> > {6, 3, 4, 9, -1}
>
> …now with 6 at position 0, 3 at position 1, and so on. Let $W\_{N\_k}$ be an ordered set of $N$ distinct $k$-wheels. Given some $W\_{N\_k}$ and some integer $t$, find a series of rotations such that…
>
> $$\forall\ 0 \leq i \< k, \sum\_{N \in W} N\_i = t$$
>
> In other words, if you laid out the wheels as a matrix, the sum of every column would be $t$. Assume that $W\_{N\_k}$ is constructed so that the solution is unique up to rotations of every element (i.e., there are exactly $k$ unique solutions that consist of taking one solution, then rotating every wheel in $W$ by the same number of steps).

The trivial solution to this problem involves simply checking every possible rotation. Here is some pseudocode for that:

```
function solve(wheels, index)
    if wheels are solved:
        return true
    if index >= wheels.num_wheels:
        return false
    for each position 1..k:
        if solve(index + 1) is true:
            return true
        else:
            rotate wheels[index] by 1

solve(wheels, 0)

```

This is a pretty slow solution (something like $O(k^n)$). I'm wondering if it is possible to do this problem faster, and also if there is a name for it.

# Answer
> 3 votes
For most of this answer, I discuss the decision version of the problem, in which an instance having at most one solution is given (the "promise"), and you have to decide whether it has any solutions or none.

You can reduce PARTITION to your problem (exercise). (PARTITION is the problem of determining whether a set of integers can be partitioned into two parts with equal sum.) Admittedly, this doesn't necessarily satisfy the condition that the solution be unique.

With some more work, you can (directly) reduce SAT to (the decision version of) your problem, and perhaps that can be done in such a way so that if the SAT instance has a unique solution, then so does the resulting instance of your problem. In that case, we get that the decision version is not solvable in polytime unless NP=RP, which is considered unlikely.

Note that if the decision version (more accurately, the promise version) of the problem is not solvable in polytime, then no algorithm can solve all YES instances in polytime: if it did, you could run it up to its allotted running time, and check the solution (if the algorithm stopped in time).

---
Tags: algorithms
---


# Question
Title: How is this algorithm in these two complexities?
How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal to, but I am not fully sure. Any have any ideas? Thanks.

# Answer
> 6 votes
The $O(\cdot)$ notation only gives an upper bound on the complexity. An algorithm has running time $O(n^2)$ if its running time can be bounded by $cn^2$ for some $c$. If it has running time $n$, say, then it's certainly bounded by $cn^2$ and so $O(n^2)$, though that's not the optimal bound.

A complement to $O(\cdot)$ is $\Theta(\cdot)$. An algorithm has running time $\Theta(n^2)$ if its (worst-case) running time is between $c\_1n^2$ and $c\_2n^2$ for some $0\<c\_1\leq c\_2$. If an algorithm is $\Theta(n\log n)$ then it is *not* $\Theta(n^2)$ (though still $O(n^2)$). In fact, even if all you know is that it is $O(n\log n)$, then that rules out $\Theta(n^2)$.

Summarizing, $\Theta$ is "exact" complexity (up to constant multiples), and $O$ is just an upper bound. There is also $\Omega$ which is for lower bounds, for example an algorithm is $\Omega(n^2)$ if its (worst-case) running time is at least $cn^2$ for some $c \> 0$.

---
Tags: algorithms, asymptotics, landau-notation
---


title: If NP $\neq$ Co-NP then is P $\neq$ NP

text:
# Question
Title: If NP $\neq$ Co-NP then is P $\neq$ NP
Does the proof of the widely believed result P $\neq$ NP depend on the proof of NP $\neq$ Co-NP ?

# Answer
> 10 votes
Only in one direction. As $\mathsf{P}=\text{co-}\mathsf{P}$, if $\mathsf{NP}\neq\text{co-}\mathsf{NP}$ then we would know that $\mathsf{P}\neq\mathsf{NP}$. However the reverse implication doesn't hold. If $\mathsf{P}\neq\mathsf{NP}$ then it's possible that either $\mathsf{NP}\neq\text{co-}\mathsf{NP}$ or $\mathsf{NP}=\text{co-}\mathsf{NP}$.

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


# Question
Title: Deciding Recursive/Recursively Enumerable when given Turning machine encoding as a language
Let $L\_{1}$ and $L\_{2}$ be two languages defined as follows :
$L\_1 = \\{ \langle M\rangle \mid L(M) \neq \emptyset \\}$
$L\_2 = \\{ \langle M\rangle \mid L(M) = \emptyset \\}$
where $\langle M\rangle$ denotes the encoding of a Turing Machine $M$. $L\_{1}$ is the set of encodings of TMs that accept at least one string (i.e. the with non-empty languages), and $L\_{2}$ is the set of encodings of TMs that do not accept any string (i.e. with empty lanugages). By making a language out of such encodings, I am essentially asking a Turing Machine to decide on another Turing machine as to whether the second TM has an empty language or not. This is essentially the halting problem, and so both languages are undecidable.

Now, I am not able to characterize $L\_{1}$ and $L\_{2}$ from among

* not recursively enumerable
* recursively enumerable but not recursive
* recursive

# Answer
As you note, both languages are undecidable, so neither are recursive. Then the remaining possiblities are recursively enumerable or not.

Note that $L\_{1} = \overline{L\_{2}}$, so if they were both recursively enumerable, then they would both be recursive, so we know at least one is not even recursively enumerable.

It turns out that $L\_{1}$ is recursively enumerable, given an input $\langle M\rangle$ we can simulate $M$ on all strings over the alphabet by interleaving the execution of $M$ on each string. It may take a long time, but if $M$ accepts something, we eventually (in finite time) find it, so we can recognise that $\langle M\rangle \in L\_{1}$.

Then simply by logical deduction, $L\_{2}$ can't be recursively enumerable, as it is already co-r.e., but not recursive.
> 3 votes

---
Tags: computability, undecidability
---