# Question
Title: Are programming languages becoming more like natural languages?
Can we study programming languages in the context of linguistics? Do programming languages evolve naturally in similar ways to natural languages?

Although full rationality, and mathematical consistency is essential to programming languages, there still is the need (especially modern languages) to make them readable and comfortable to humans.

Are programming languages evolving to become more linguistic and thus more natural? For example machine code, punch cards and assembly languages have given way to more readable languages like Ruby and Python etc.

When I say computer languages are becoming more natural, I don't mean they contain more 'words we have in english', I mean they seem to becoming more like a natural language, in terms of their complexity of grammer and ability to express meaning (for example, being able to eloquently describe a query from a database in both rational and human understandable ways).

What do you all think? Are programming languages becoming more like natural languages, and thus becoming applicable to the laws of Linguistics?

Or perhaps languages live on a spectrum, where on one side you have the extreme rational languages and the other the more creative. Maybe, programming and natural languages are identical and both just lie on this language spectrum (their only difference, perhaps being the 'thing' they are trying to give their meaning to).

Is there a connection between the (Babel Tower effect) separation of human languages and of computer langages? Do they become more diverse for the same reasons (i.e. to solve different problems within ever-evolving computer-systems/culture-systems etc.)?

# Answer
Not really, no. Programming languages have become more like natural languages only in the sense of “words we have in english” (*sic*).

A key feature of programming languages is that they are not ambiguous. When you write a program and execute it, it has a well-defined meaning, which is its behavior. If you want to write a program that works as intended (a difficult objective), it is important that the behavior¹ of the program be as predictable as possible. Programming languages haven't made much difference in the wide gap towards natural languages.

Conversely, there has been work in bridging the gap from the other side: analyzing natural languages with the same tools as programming languages. This field is called natural language processing. These approaches have been pretty much discarded in favor of machine learning. I'll cite a passage in the Wikipedia article which is directly relevant here:

> Up to the 1980s, most NLP systems were based on complex sets of hand-written rules. Starting in the late 1980s, however, there was a revolution in NLP with the introduction of machine learning algorithms for language processing. This was due both to the steady increase in computational power resulting from Moore's Law and the gradual lessening of the dominance of Chomskyan theories of linguistics (e.g. transformational grammar), whose theoretical underpinnings discouraged the sort of corpus linguistics that underlies the machine-learning approach to language processing.

One way in which programming is evolving is that as we design larger and larger systems, source code is not always a good way of understanding them. For example, an Intel CPU is one of the most complex objects ever designed by Man, and its “source code” is not just a collection of text files, far from it. But the full design isn't evolving towards anything resembling a human language either. I don't know what the appropriate cognitive tools or metaphors here, and I don't think anybody knows just yet; ask again in a couple of centuries.

¹ <sub> Or rather the set of possible behaviors annotated with the circumstances under which they arise, but that's only adding one step of indirection in the modeling, so this isn't really relevant here. </sub>
> 32 votes

# Answer
an interesting case study in this area is Perl vs Ruby (and Python). Perl is a scripting language developed in early 90s that added much capability compared to prior Unix based scripting languages (eg bash). the author Larry Wall is on record as saying his background in linguistics inspired some of the language features.

however Perl has awkward syntax and many special cases that make the language somewhat like English in all its subtle idiosyncracies inspiring various levels of criticism. later scripting languages like Ruby and Python, developed by computer scientists, have much more consistency in their syntax. the main problem is that natural language has large amounts of ambiguity (this is studied in the field of linguistics.) so natural language will have a key place on future human-computer interfaces like Siri but those interfaces will inherently be subject to ambiguity problems.

so, here is a case where the evolution of computer languages went *away* from a natural language idea. moreover, the general history of computer programming languages is that they have been developed and changed to *remove* ambiguity (which is highly inherent to natural language). this was not understood early in the history of compilers (say possibly in the 1970s) and eg early versions of the Fortran language had statements with ambiguous meanings that depended on compiler implementation. some of CS language theory related to parsing was developed partly in response to the discovery of ambiguity in language parsing.
> 2 votes

# Answer
Computer languages tend to do well with terseness and precision, somewhat like mathematical notation, which has shown no particular inclination to evolve towards natural language (that I'm aware of) over the past few thousand years.

I also doubt that if you communicated with your infant exclusively in Haskell for the first few years of his life he would develop natural language fluency. So, I think there is pretty sharp contrast between natural and computer languages.

Perhaps wider spread of language construction techniques have improved the "naturalness" slightly over time, I suppose, since programmers "vote with there feet" by using languages that seem easier to them and the number of people capable of creating languages has gone up with more practitioners and better tools, but this is a small effect around the edges and doesn't represent a fundamental transformation of programming languages into human ones.
> 1 votes

# Answer
Machine language is very precise, while a human-written text can usually be interpreted in many different ways (some poetic text for example).

What is more and more evolved is patterns matching, for example when you write some ugly code a compiler can help you proposing several possible solutions and then throw some warning or error that can help you exprime yourself. (based on common code patterns for example)

There is specific research on interaction/design patterns, even T9 and SWYPE are patterns recognizers that help a lot you (programs that records your voice and convert it to text are patterns recognizers too).

Of course a program is something that relies on precise mechanisms so you need precise languages (not natural), while a simple web search on google is very natural, you just have to type few words and you get what you want.

Every different task and goal has its own language, that's not a simple "single language evolution" there are much more languages. Precise tasks need precise languages and relaxed tasks requires relaxed languages

You can write the same piece of C code and then compile it with several different compilers, and (unless some compiler is bugged) the result of the code will be the same even if different assembly is generated, while for a web search givin the same keywords to different search engines gives different results.
> 1 votes

# Answer
Some years ago my elder son and I developed a Plain English programming and development system in the interest of answering the following questions:

1. Can low-level programs (like compilers) be conveniently and efficiently written in high level languages (like English)?
2. Can natural languages be parsed in a relatively "sloppy" manner and still provide a stable enough environment for productive programming?
3. Is it easier to program when you don't have to translate your natural-language thoughts into an alternate syntax?

We can now answer each of these three questions, from direct experience, with a resounding "Yes".

Our parser operates, we think, something like the human brain. Consider. A father says to his baby son:

"Want to suck on this bottle, little guy?"

And the kid hears,

"blah, blah, SUCK, blah, blah, BOTTLE, blah, blah."

But he properly responds because he's got a "picture" of a bottle in the right side of his head connected to the word "bottle" on the left side, and a pre-existing "skill" near the back of his neck connected to the term "suck". In other words, the kid matches what he can with the pictures (types) and skills (routines) he's accumulated, and simply disregards the rest. Our compiler does very much the same thing, with new pictures (types) and skills (routines) being defined -- not by us, but -- by the programmer, as he writes new application code.

A typical type definition looks like this:

A polygon is a thing with some vertices.

Internally, the name "polygon" is now associated with a type of dynamically-allocated structure that contains a doubly-linked list of vertices. "Vertex" is defined elsewhere (before or after this definition) in a similar fashion; the plural is automatically understood.

A typical routine looks like this:

To append an x coord and a y coord to a polygon: Create a vertex given the x and the y. Append the vertex to the polygon's vertices.

Note that formal names (proper nouns) are not required for parameters and variables. This, we believe, is a major insight. My real-world chair and table are never (in normal conversation) called "c" or "myTable" -- I refer to them simply as "the chair" and "the table". Likewise here: "the vertex" and "the polygon" are the natural names for such things.

Note also that spaces are allowed in routine and variable "names" (like "x coord"). This is the 21st century, yes? And that "nicknames" are also allowed (such as "x" for "x coord"). And that possessives ("polygon's vertices") are used in a very natural way to reference "fields" within "records".

Note, as well, that the word "given" could have been "using" or "with" or any other equivalent since our sloppy parsing focuses on the pictures (types) and skills (routines) needed for understanding, and ignores, as much as possible, the rest.

At the lowest level, things look like this:

To add a number to another number: Intel $8B85080000008B008B9D0C0000000103.

Note that in this case we have both the highest and lowest of languages -- English and machine code (albeit in hexadecimal) -- in a single routine. The insight here is that (like a typical math book) a program should be written primarily in a natural language, with appropriate snippets in more convenient syntaxes as (and only as) required.

You can get our development system here: www.osmosian.com/cal-3040.zip . It's a small Windows program, less than a megabyte in size. If you start with the PDF in the "documentation" directory, before you go ten pages you'll be recompiling the whole shebang in itself (in less than three seconds on a bottom-of-the-line machine from Walmart).

Questions and comments should be addressed to gerry.rzeppa@pobox.com
> 1 votes

# Answer
Separation of human languages come from (darwinian ?) evolution in isolated communities. Separation of programming languages comes from variations in technical need, technical ideology, from changes in technical and theoretical understanding, from changes in our technical ability to implement. It is a somewhat more conscious process, I think.

Could computer languages be more like natural languages ? Probably somewhat, up to a point. I guess that a large part of natural language complexity results from a variety of concurrent evolution phenomena that have no reason to produce a consistent result at any one point in time, even though it is likely that old inconsistencies are probably progressively eliminated while new one appear. I am no expert in diachronic linguistics. But do we want that kind of complexity in programming languages.

The issue of ambiguity is an important one, but not as stated by most people. A language is a mean of communication, and it must be analyzed in the context of that communication (man-man, man-machine, both, between places or between times, ... to say it a bit simplistically). What matters is not whether you can make only unambiguous statements in the language, but whether you can always ensure that the communication will be unambiguous in its intended context. There is one well known and widely used programming language, that allows writing ambiguous programs (well, it did, but I have not looked at the latest versions for a while). In this case, the compiler is smart enough to detect the ambiguity and ask for clarification, which can be incorporated in the program the eliminate the ambiguity. Note that ambiguity detection does not mean that only one of the possible choices has meaning, they all do. The issue is whether one of the communicating entities can detect the ambiguity so that the sender can clarify it. Human beings are bad at this, but computers can be pretty good.

Formalisms and programming languages could have richer and more flexible syntax. I believe the main reason they do not is simple conservatism. The syntactic tools used are still very often tools designed thirty years ago or more, to meet the limitations of the computers of that time. Parsing efficiency is no longer such a critical issue in compiling and more powerful techniques do exist tractably.

Interestingly, the most widely used basis for programming languages syntax comes from natural language research : the context-free grammar. Much of the technical research moved the to theoretical/technical computer science in the sixties, to be somewhat rediscovered in the early eighties by natural language people (I am simplifying). Since then, much progress has been made for syntax in natural languages, while computer science seems largely stuck with old syntactic tools. The natural language pendulum is now swinging again towards statistical techniques, but algebraic approaches for syntax are not forgotten. Most likely, good approaches will come from a combination of algebraic and statistical techniques.

My feeling is that the critical area is semantics and the transition between syntax and semantics. This is still very hard to formalise for natural language, while we have many precise techniques in the case of programming languages and formal systems. As the game is far from being played for natural languages, it is hard to say what impact it could have on programming languages in the future.

Another point is that many programming language designers are trying to prove something or enforce a technical ideology. Thus they get extremely prescriptive in their design to prevent users from departing from their intended paradigms. This is unfortunately extremely counter-productive for creativity. The most creative language ever designed was among the very first : Lisp (1958). The freedom and flexibility it allowed was the source of considerable creativity. The price was that it required self-discipline and understanding. But Lisp was really a metalanguage, a language for the creation of languages.

Now, to take another perspective, programs are actually proofs of their specification seen as a mathematical statement (well, I am simplifying again). Some people (I do not remember references, sorry) have been playing with theorem provers to produce proofs that would look like they had been written by a mathematician in natural language. So I guess the idea of having programs that look like they were written in natural language may not be totally absurd.

You may however notice that, even when written informally by a mathematician, mathematical discourse looks quite different from ordinary talk, or from a history book. This is due to a significant difference in the concerned universe of discourse, the semantic domains that are being talked about. Thus while you can envision programming languages that look more like natural languages, there is a natural limitation which is the domain of discourse and its own desirable properties. Most likely it will remain essentially superficial, that is, mostly syntactic. The mathematician can talk about formal systems and about politics. Hopefully the two discourses will not look similar. Computers cannot (yet?) talk of politics, or understand it. The day they do it will no longer be programming.

Looking back in history, high level languages were, from the very first (FORTRAN) an attempt to get closer to a more natural form to express computational tasks, but these tasks were understood as mathematical or logical (Fortran 1957, Algol 1958, Lisp 1958), or more business oriented (Cobol 1959). Within 10 years people were worrying about languages that would be closer, better adapted to the problem at hand, and there was significant research in so-called `extensible
languages`, covering both syntax and semantics. One major pathway for expressing problems more naturally was the emergence of `object
orientation` (sometimes under other names). Though it is always difficult to assign parenthood, it probably emerged from the work on artificial intelligence, mostly in Lisp, and from the language `Simula
67` (Algol family) which was itself intended to express more naturally real world problems that are to be simulated on a computer. It all seems historically consistent.
> 1 votes

# Answer
Although they are similar in that the asked questions are similar, they are quite distinct in terms of complexity. The main difference is that natural language is inherently ambiguous (even at the level of words). It is even not clear what is meant by a word? In the world of programming languages however, a variety of defining devices are at disposal. Look at grammars for parsing natural language and those for parsing programming languages, the difference in size is stunning. The thing is That grammars for programming languages are formal systems; so they are amenable to mathematical analysis. Dealing with ambiguities pops up many problems for which a solution in the programming language counterpart would be trivial or simple.

Maybe the gap between natural languages and programming languages will shrink if the gap between computer scientists and "natural" people shrinks.
> 0 votes

# Answer
In the past years, the interest in (E)DSLs and fluent interfaces has been steadily on the rise, in a great variety of languages: Haskell, the various scripting languages, C#, Java, and even C++ (think of the overloading of `operator<<` for doing output).

To some extent, these allow code to read more naturally. I'll illustrate with an EDSL example in groovy. The groovy.time package allows you to write

```
use ( TimeCategory ) {
    // application on numbers:
    println 1.minute.from.now
    println 10.days.ago

    // application on dates
    def someDate = new Date()
    println someDate - 3.months
}

```

If you were to do this via the java.util.Calendar class you would have to write something like this for the first example:

```
void demo() {
    Calendar date = new GregorianCalendar();
    date.add(Calendar.MINUTE, 1);
    System.out.println(date);
}

```
> 0 votes

# Answer
Computer languages (even the rudimentary machine languages of days long past) *are* human languages, as they are primarily for communication with fellow human beings, are defined by humans, and are used only secondarily to convey instructions to a machine. So they evolve much the same way "natural" languages evolve (just look up "idioms" for your favorite language, check on how e.g. C has evolved from K&R C to current ISO-C 2011. But they exist in a different environment, they must convey precise meaning (computers are still too dumb to make sense and correct what is asked of them), and there is a premium on ease of processing (thus the grammar and vocabulary of even C++, PL/1, or APL are *much* simpler than e.g. English, which as natural languages go is rather simple).

Much the same thing can be said of the formalism of mathematics or the sciences in general, or even blueprints (inherently 2D, not 1D as the others are).
> 0 votes

---
Tags: programming-languages, natural-language-processing
---


# Question
Title: Is it legal to use non-terminal twice in Backus-Naur grammar
It's a school assignment: The problem is: Write a BN grammar for +67.

The given solution I have been given is following:

```
<digit>  ::= 6 | 7
<number> ::= <digit> | <digit> <number>
<+67>    ::= + <number>

```

My question is, when given this simple task, could it be derived like this?

```
<digit>  ::= 6 | 7
<number> ::= <digit> <digit>
<+67>    ::= + <number>

```

More precisely, can I use same non-terminal twice in same rule?

# Answer
> 6 votes
Yes, you are allowed to use the same non-terminal more than once in a rule.

Note that the two grammars you give do not express the same set of strings. The first grammar gives any sequence of 6 or 7 following the +, as can be applied recursively. The second defines exactly four strings +66, +67. +76, +77.

---
Tags: terminology, formal-grammars
---


# Question
Title: Deterministic Turing Machine with infine tape in both directions
Consider a deterministic Turing Machine $D$ which has an infinite tape in both directions. We don't have exact information about it; what we know is that its alphabet is $\\{a, b, c\\}$ and there are at least three states $q\_1, q\_s, q\_f$ where $q\_s$ is the start state, $q\_f$ is the final state. At some step of the computation, all the tape is blank except one cell containing the symbol $a$, the state is $q\_1$ and the head is currently at a blank cell.

I need to write states and transitions that will guarantee to enter to final state from state $q\_1$ but I have difficulties since $D$ is both deterministic and with infinite tape in both directions.

# Answer
You can design a Turing Machine that goes one step left, then two right, then 3 left and so on... You don't need too much states for that: just put two markers on the tape: $b$ for the current left boundary and $c$ for the current right boundary of what you explored, and push them back from one cell each time you reach them. You have one state $q\_b$ going left until $b$ is reached, and one state $q\_c$ going to the right until $c$ is reached. Plus special states to shift them by one position.

You will eventually find the $a$ letter, at which point you just go to $q\_f$.
> 4 votes

---
Tags: turing-machines
---


# Question
Title: What does the R superscript notation mean in regular/formal languages?
What does the capital R superscript notation mean in regular languages? I am working on a homework assignment and don't recall my professor mentioning what the what the R superscript means. For example in this syntax:

$L = \\{ww^R\mid w \in \Sigma^{\ast} \\}$

# Answer
> 6 votes
Reverse. So for example $(001)^{R} = 100$. Or to overdo it, for an string $s = s\_{1}s\_{2}\ldots s\_{n}$, the reverse $s^{R}$ is $s\_{n}s\_{n-1}\ldots s\_{2}s\_{1}$.

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


# Question
Title: Show that the equivalence problem for deterministic Turing machines and its complement is not semi-decidable
I would like to show that $$EQ\_{DTM} = \\{ (\langle M\_1\rangle,\langle M\_2\rangle) \mid M\_1\text{ and } M\_2 \text{ are DTMs and } L(M\_1)=L(M\_2)\\}$$ and $$\overline{EQ\_{DTM}}$$ are not semi-decidable. I think there must be a reduction from the complement of the halting problem.

# Answer
I think an easier way to approach this is by reducing from $$ALL\_{TM}=\\{\langle M \rangle: M \text{ is a DTM and } L(M)=\Sigma^\*\\}$$

Showing that $ALL\_{TM}$ is not in in RE nor coRE a standard exercise, and you can find the solution e.g. here

Then, we can reduce from $ALL\_{TM}$ to $EQ\_{TM}$ as follows: given input $\langle{M\rangle}$ for $ALL\_{TM}$, we output $\langle{M,T\rangle}$ where $T$ is a fixed TM that accepts every input immediately. Thus, $L(T)=\Sigma^\*$, and we have that $L(M)=L(T)$ iff $L(M)=\Sigma^\*$, so the reduction is correct.
> 2 votes

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


title: Definability of Truth Assignments

text:
# Question
Title: Definability of Truth Assignments
I have a question about definability of truth assignments. Suppose that I am working in the context of propositional logic. Let me give some definitions first.

Let $L$ be a propositional language with the set $Prop\_{L}$ of propositional variables. A truth assignment is a map $v\colon Prop\_{L}\to\\{F,T\\}$. Denote the collection of truth assignments in $L$ by $TA\_{L}$. Note that in a language $L$ with $|Prop\_{L}|=n$ for some $n\in\mathbb{N}$, $|TA\_{L}|=2^{n}$, while in a language with $|Prop\_{L}|=\aleph\_{0}$ (denumerably many), $|TA\_{L}|=2^{\aleph\_{0}}=\mathfrak{c}$ (continuum many).

**Definition 1.** Let $\Sigma$ be a set of propositional formulas. The set of **models** of $\Sigma$ is $$Mod(\Sigma):=\\{v:v\ \mbox{is a truth assignment and $v(\varphi)=T$ for each $\varphi\in\Sigma$}\\}.$$

**Definition 2.** Let $K\subseteq TA\_{L}$. Then $K$ is **definable** if $K=Mod(\Sigma)$ for some set $\Sigma$ of formulas.

I have tried to prove a couple of things. In a propositional language with *only finitely many* propositional variables, any set of truth assignments is definable. Now, I want to show that, in a propositional language with *denumerably many* propositional variables, any *finite* set of truth assignments is definable. Imitating the idea in the proof about finite language, I have an outline of the proof about infinite language. Here is the detail:

**Convention.** Let $p$ be a propositional variable and $v$ a truth assignment. Define $$ p^{v}:= \begin{cases} p &\mbox{if}\ v(p)=T;\\ \neg p &\mbox{otherwise}. \end{cases} $$ Then it can be seen easily that $\widehat{v}(p^{v})=T$. (Here $\widehat{v}$ denotes the extension of $v$ to the set of propositional formulas.)

**Claim.** In a language $L$ with $|Prop\_{L}|=\aleph\_{0}$, any finite set of truth assignments is definable.

*Proof.* Assume that $Prop\_{L}=\\{p\_{1},p\_{2},\ldots\\}$. Let $K\subseteq TA\_{L}$. Assume that $K$ is finite. Then $K=\\{v\_{1},v\_{2},\ldots,v\_{k}\\}$ for some $k\in\mathbb{N}$. Let $1\leq i\leq k$. For each $j\in\mathbb{N}$, define $$\varphi^{i}\_{j}:=p^{v\_{i}}\_{1}\wedge p^{v\_{i}}\_{2}\wedge\cdots\wedge p^{v\_{i}}\_{j}$$ and define $$\chi\_{j}:=\varphi^{1}\_{j}\vee\varphi^{2}\_{j}\vee\cdots\vee\varphi^{k}\_{j}.$$ Let $\Sigma=\\{\chi\_{j}:j\in\mathbb{N}\\}$. Claim that $K=Mod(\Sigma)$.

Now, the part $K\subseteq Mod(\Sigma)$ is easy. What is hard for me is the reverse inclusion: any truth assignment satisfying $\Sigma$ must be $v\_{i}$ for some $1\leq i\leq k$. Since I am dealing with infinitely many propositional variables, to show that two truth assignments coincide is to show that they agree on infinitely many propositional variables. Yet I have no idea how to show that, because truth assignments in $K$ seem to involve only finitely many propositional variables. Could anyone please advise me about this?

Any suggestions would be greatly appreciated :)

# Answer
> 4 votes
Let $T=\\{\tau\_1,\cdots, \tau\_k\\}$ be the set of truth assignments. Consider the tree of the truth assignments $2^\omega$.

Consider the formula $\Gamma\_T = \\{ \underset{\tau \in T}\lor \tau\_{|n} \mid n \in \omega\\}$ where $\tau\_{|n}$ is the formula that expresses $\tau$ up to atom $p\_n$, i.e. $\underset{i\leq n}\wedge l\_i(\tau)$ where $l\_i(\tau) = \begin{cases} p\_i & \tau(p\_i)=\top \\ \lnot p\_i & \tau(p\_i)= \bot \end{cases}$.

It is easy to show that every $\tau \in T$ we have $\tau \vDash \Gamma\_T$.

For any $\tau \notin T$, there is some $n\in \omega$ such that $\tau\_{|n}$ is different from those in $T$ and therefore $\tau$ does not satisfy $\underset{\tau \in T}\lor \tau\_{|n}$ and therefore $\tau\nvDash \Gamma\_T$.

There is a topological characterization of the sets of truth assignments that can be defined. Consider $2^\omega$ as space of points with product topology. Consider the sets of points that can be captured using sets of formulas. They are closed under finite unions (consider the disjunctions of the pairs of formulas from the product) and arbitrary intersections (union of two sets).

You may be interested in Stone duality and type (model theory).

# Answer
> 1 votes
Your proof seems ok, by the following argument:

Let $v$ be a truth assignement satisfying $\Sigma$. Then for each $j\in\mathbb{N}$, $v$ has to satisfy at least one of the $\varphi\_j^i$ (where $i\in\[1,k\]$).

Therefore, there is $i\in\[1,k\]$ such that infinitely many of the $\varphi\_j^i$ are satisfied by $v$. This is enough to conclude that $v=v\_i$.

---
Tags: logic
---


# Question
Title: In control flow graphs, what is the difference between a path and a branch?
I'm studying for an exam on software testing and in my notes I found this:

```
Many more paths than branches. A pragmatic compromise will be needed

```

I cannot understand the difference between paths and branches; each time I work out the paths and branches of a graph I end up with the same number. Thanks!

# Answer
> 3 votes
I do not know the exact definitions used by your class, so I am saying this with caution. A branch normally correspnds to a graph edge that allows control to pass from one node to another in the graph. A path is a succession of edges connected to each other, with possible repetition and representing the successive parts traversed by the control. So a branch will be a element of the program structure, a static entity. The path represent a fragment of computation.

If you say more about what you understood, I may be able to tell you whether it makes sense.

---
Tags: algorithm-analysis, software-testing
---


# Question
Title: What is a "wasteful" execution? And a "schedule"?
I'm trying to understand what this text means in my textbook about distributed leader election algorithms, but I can't make any sense of it. Either they didn't explain what was meant, or I missed it somewhere.

> In this section, we show that the leader election algorithm of Section 3.3.2 is asymptotically optimal. That is, we show that any algorithm for electing a leader in and asynchronous ring sends at least $\Omega(n\log n)$ messages. The lower bound we prove is for uniform algorithms, namely, algorithms that do not know the size of the ring.
>
> We prove the lower bound for a special variant of the leader election problem, where the elected leader must be the processor with the maximum identifier in the ring; in addition, all the processors must know the identifier of the elected leader. The proof of the lower bound for the more general definition of the leader election problem follows by reduction.
>
> Assume we are given a uniform algorithm $A$ that solves the above variant of the leader election problem. We will show that there exists an admissible execution of $A$ in which $\Omega(n\log n)$ messages are sent. **Intuitively, this is done by building a "wasteful" execution of the algorithm for rings of size $n/2$, in which many messages are sent.** Then we "paste together" two different rings of size $n/2$ to form a ring of size $n$, in such a way that we can combine the wasteful executions of the smaller rings and force $\Theta(n)$ additional messages to be received.
>
> Although the preceding discussion referred to pasting together exections, we will actually work with **schedules**. The reason is that executions include configurations, which pin down the number of processors in the ring. We will want to apply the same sequence of events to different rings, with different numbers of processors. Before presenting the details of the lower bound proof, we first define schedules that can be "pasted together".
>
> *A schedule $\sigma$ of $A$ for a particular ring is open if there exists an edge $e$ of the ring such that in $\sigma$ no message is delivered over the edge $e$ in either direction; $e$ is an open edge of $\sigma$.*

There is lots more, but I don't know if I should type it all out if only for copyright reasons. I hope this is enough to help clarify my question and get an explanation.

# Answer
> 2 votes
I'm not completely sure of my answer since I don't have the book but I think that:

By "wasteful" execution they mean an execution that follow $A$ but with a lot of messages. There are trying to prove that for $n$ processes you may need $\Omega(n\log(n))$ messages. So they consider a ring with $n/2$ processes and the worst execution and they want to combine two of this rings and of those executions to prove that for $n$ processes you will need a least $n\log(n)$ messages.

By scheduler I think the mean a function $\sigma$ that a each state of your system associate a process and an action to be performed. A fixed system and a scheduler are equivalent to an execution (since you can see it as $s\xrightarrow{\sigma(s)}s\_1\xrightarrow{\sigma(s\_1)}s\_2\xrightarrow{\sigma(s\_2)}\dots$ But schedulers are often more easy to work with since they are functions so in the proof you don't need to manipulate indexes of where you are in the execution.

I hope it helps, please ask if I missed something.

---
Tags: algorithms, distributed-systems
---


# Question
Title: All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?
My book states this

> * If a decision problem B is in P and A reduces to B, then decision problem A is in P.
> * A decision problem B is NP-complete if B is in NP and for every problem in A in NP, A reduces to B.
> * A decision problem C is NP-complete if C is in NP and for some NP-complete problem B, B reduces to C.

So my questions are

> 1. If B or C is in NP-complete, and all problems in NP reduce to an NP-complete problem, using the first rule, how can any NP problem not be NP complete?
> 2. If A reduces to B, does B reduce to A?

# Answer
> If A reduces to B, does B reduce to A?

No. For a really contrived example, any possible computable problem A is reducible to the Halting Problem: just pass as input the algorithm that solves the problem A but with a `while(true)` tacked at the end after either the true or false case. However, we know that the Halting problem isn't computable so it can't be reduced to any such algorithm A.

The basic idea is that if there is a reduction from A to B you can learn that B is at least as hard to solve then A and requires an algorithm that is at least as powerful.

So if a problem A reduces to an easy problem B, then we can deduce A is easy (since the reduction gives us the efficient algorithm) and if a hard problem A reduced to a problem B, we can deduce that B is also hard (since if B were easy then A would have to be easy too). However there is still the possibility of making a silly reduction from an easy problem to a hard problem but in this case we can't deduce any conclusions.
> 14 votes

# Answer
> If B or C is in NP Complete, and all problem in NP reduce to an NP Complete problem, using the first rule, how can any NP problem not be NP complete?

The first rule is about problems in P. It has nothing to do with NP completeness. If problem A is NP Complete and problem B reduces to A, that does **not** mean that B is NP Complete.

> If A reduces to B does B reduce to A?

Not generally, no.
> 10 votes

# Answer
I have only the basic idea regarding NPC and NP Problems. But All i want to comment is about "If A is reduced to B then B is reduced to A? "

Simply consider a set A having {2,3,4,5} elements and set B having {3,4} in it. So A can be reduced to B. But B can't be reduced to A. Instead B can be expanded to A if B gains {2,5} elements.

But if A and B are having the same. then A can be reduced to B or B can be reduced to A.
> -2 votes

---
Tags: complexity-theory, np-complete, decision-problem
---


# Question
Title: Trouble understanding this dynamic programming solution
Here is the question:

I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K.

for example: If `n=3` and `k=1`

and the given tree is `1---2---3`

Then the total valid subtrees would be 6

```
{}, {1}, {3}, {1,2}, {2,3}, {1,2,3}

```

I know I can enumerate all `2^n` trees and chack the valid ones, but is there some approach that is faster? Can I achieve polynomial time in `n`? Something close to `O(n^3)` or even `O(n^4)` would be nice.

for k=1 this value turns out to be `2*n`

**There was a solution provided for this one as:**

This is a fairly typical instance of the DP-on-a-tree paradigm. Let's generalize the problem slightly by allowing the specification of a root vertex v and stratifying the counts of the small-boundary trees in two ways: whether v is included, and how many edges comprise the boundary.

The base case is easy. There are no edges and thus two subtrees: one includes v, the other excludes v, and both have no boundary edges. Otherwise, let e = {v, w} be an edge incident to v. The instance looks like this.

```
|\         /|
| \   e   / |
|L v-----w R|
| /       \ |
|/         \|

```

Compute recursively the stratified counts for L rooted at v and R rooted at w.

Subtrees that include v consist of a subtree in L that includes v, plus optionally e and a subtree in R that includes w. Subtrees that don't include v consist of either a subtree in L that doesn't include v, or a subtree in R (double counting the empty tree). This means we can obtain the stratified counts by convolving the stratified counts for L with the stratified counts for R.

Here's how this works on your example. Let's choose root 1.

```
  e
1---2---3

```

We choose e as shown and recurse.

```
1

```

The vector for includes-1 is \[1\], since the one subtree is {1}, with no boundary. The vector for excludes-1 is \[1\], since the one subtree is {}, also with no boundary.

```
2---3

```

We compute 2 and 3 as we did for 1. The vector for includes-2 is \[1, 1\], since {2, 3} has no boundary edges, and {2} has one. We obtained this vector by adding the includes-2 vector for 2, shifted by one because of the new boundary edge to make \[0, 1\], to the convolution of the includes-2 vector for 2 with the includes-3 vector for 3, which is \[1, 0\]. The vector for excludes-2 is \[1\] + \[1, 1\] - \[1\] = \[1, 1\], where \[1, 1\] is the sum of the shifted includes-3 vector and the excludes-3 vector, and the subtraction is to compensate for double-counting {}.

Now, for the original invocation, to get the includes-1 vector, we add \[0, 1\], the includes-1 vector for 1 shifted by one, to the convolution of \[1\] with \[1, 1\], obtaining \[1, 2\]. To check: {1, 2, 3} has no boundary, and {1} and {1, 2} have one boundary edge. The excludes-1 vector is \[1\] + \[1, 2, 1\] - \[1\] = \[1, 2, 1\]. To check: {} has no boundary, {2, 3} and {3} have one boundary edge, and {2} has two boundary edges.

**I am unable to understand this fully. Can anyone help?**

# Answer
> 2 votes
The problem is to count the subtrees of an undirected tree that have at most k outgoing edges to the rest of the tree.

The idea of the algorithm is a divide and conquer plus dynamic programming technique. For a tree T, you divide it into 2 subtrees, and for each you compute all subtrees that have i outgoing edges for each i less than or equal to k. There is however a little twist to allow the recurrence step to work. The divide and conquer part is not really necessary, but it does allow a simpler organization.

---

I agree that the explanation of the algorithm that you were given is somewhat obfuscated.

`small-boundary trees` are what you called `valid trees`, with at most k out-going edges.

Consider your tree T.

Though in your undirected tree T all nodes are born equal, you choose to distinguish a root v.

The idea is to count the number of subtrees for each value of the number of outgoing edges, an also separate those that contain the root v from those that do not.

Hence you have two vectors Tv+ and Tv--, for the subtrees including v and for the subtrees not including root node v. Tv+\[i\] is the number of subtrees including V that have i outgoing edges. Tv-\[i\] is the number of subtrees not including V that have i outgoing edges.

The sum of these two vectors will give you the number of subtrees with i outgoing edges for each value of i less than or equal to k. At this point the distinction into two vectors has not been useful, but it is needed for the recursion.

Before using them, you have to compute these two vectors.

For that purpose, you choose an edge e={v,w}, which cuts your tree T in two subtrees L and R, respectively rooted in v and w as shown on the figure

```
|\         /|
| \   e   / |
|L v-----w R|
| /       \ |
|/         \|

```

Suppose you have computed the vectors Lv+, Lv-, Rw+ and Rw-, then you can use the results in those 4 vectors to compute Tv+ and Tv- as explained in the document.

`Subtrees that include v consist of a subtree in L that includes v,
plus optionally e and a subtree in R that includes w.`

translates into :

`Tv+[i] = Lv+[i-1] + sum (Lv+[j] * Rw+[k]) for all (j,k) such that j+k=i` , for `i>0`

`Tv+[0] = 1` Only the whole tree T contains v and has no outgoing edges.

The `i-1` in `Lv+[i-1]`is to account for the added outgoing edge {v,w}

The sum of products is for all subtrees that include the edge {v,w}, and thus have a part in L and another in R.

`Subtrees that don't include v consist of either a subtree in L that
doesn't include v, or a subtree in R (double counting the empty tree).`

translates into :

`Tv-[i] = Lv-[i] + Rw+[i-1] + Rw-[i]` for i\>0

`Tv-[0] = 1` for th empty tree `{}`

The `i-1` in `Rw+[i-1]` is for the fact that subtrees counted in Rw+ get an extra edge {v, w} in the recurrence step since v is not included

There is empty tree in `Lv-[i]` and another in `Rw-[i]`, but it does not matter as empty trees are considered in the case i=0.

hoping I did not miss anything.

Is this enough to get you started, or do you need more?

One last point. The description of the algorithm starts by saying that it will consider the count of `small-boundary trees`, which I believe are your `valid trees`. If you know in advance the value of k (defining them) that you do not wish to exceed, then you vectors need only have length k+1. For example, if k=1, the vectors should be of length 2 (for zero edges and for 1 edge). Any subtree that exceeds k edges will be useless for the rest of the algorithm (the count cannot go down) and can thus be forgotten.

Note that, as described, the original algorithm uses variable size arrays, only as long as needed for the subtree at hand. That is required if you do not fix k in advance. If you do, you just use length k+1 as I said.

But this is a personnal remark that you may or may not trust. It is not in the algorithm you have been given.

---
Tags: algorithms, graphs, dynamic-programming, trees
---


# Question
Title: Complexity of a hash tables with balanced trees in the buckets
If I use a balanced tree instead of lists in a hash table implementation, and also after initializing my table I don't enlarge nor reduce the size of the table, what would be the worst case complexity?

# Answer
> 2 votes
1. If you take a table of size 1 (the smallest possible case), what is the complexity?
2. If you take a table of size 42, what is the complexity?
3. If you take a table of size 2013, what is the complexity?
4. If you take a table of size $n$, what is the complexity?

> It's always the complexity of the balanced tree. Times a constant, which doesn't change the big oh.

---
Tags: time-complexity, hash, hash-tables
---


# Question
Title: Finding least number of line segments with length $L$ that cover $N$ points
The problem is defined as:

> Given $N$ points on an infinite line, find the least number of line segments of length $L$ that cover all points (including endpoints) after changing one point.

That means that if I have the points $P = 1,10,15,28$ , $L = 10$ , 3 line segments are needed , changes will occur that the point $i$ will move to position $X$ , after each change , get the number of line segments needed.

Example:

$P = 1,5,11,21,25$ , $L = 6$ , Changes are

$$ 1 , 29 $$

$$ 2,36 $$

after change #1 : $P = 5,11,21,25,29$ , number of line segments needed is 3

after change #2 : $P = 11,21,25,29,36$ , number of line segments needed is 4

What would be the best approach to do this? , Given that number of points can be $50,000$ and the number of changes can be $50,000$.

# Answer
> 1 votes
Point indexes are just a way of naming them. What matters in the algorithm is only their positions.

The first thing you need is the management of your points. You need a structure that sorts them according to position when given the initial list of positions (ascending or descending order, it does not matter). This structure must allow you to remove a point, and add it somewhere else at low cost to keep the list sorted when you operate a change. You will find many such structures in any course on data structures and algorithms.

Then you need a structure for representing segments that will group your points into a collection of buckets of points covered by the same segment. This collection of buckets is a covering. The construction of an optimal covering is easy. You can show easily that, given any covering, you can always replace the lefmost segment by a segment that start rightward at the leftmost point, to get another covering. From that you can show by induction that you can get an optimal covering by placing a segment so that its leftmost end is on the leftmost point, and then reapeat recursively starting at the lefftmost point not yet covered.

A symetric proof shows that you can alternatively start from the right. Actually, combining the two proofs, you can show that you can always chose your next segment either rightward from the leftmost point or leftward from the rightmost point, computing from both end towards the middle until the two computations "meet" somewhere in the middle (you can choose that "somewhere"). In all versions of the algorithm, the last segment added may cover points that are already covered (though it can be avoided for the unidirectionnal versions of the algorithm - it does not matter anyway).

We assume first you build your covering from the left only.

Each change is composed of two "half-changes", removal of the point from its former position followed by addition of the point in the sorting structure at its new position. After performing them, you have recompute your segments. You try to limit the new computation to an incremental change to the previous one, and you must have kept your collection of buckets. You start at the leftmost segment affected by the leftmost "half-change" (either addition or removal), and you recompute segments until you find a segment that is the same as for the previous covering (which ends a first incremental update), and you do some accounting to know whether and how that changes the number of segments. If the rightmost "half-change" has been passed in the process, you are also done for that change. Else you do the same for that second half-change, still recomputing from left to right as in the first computation of a minimal covering of segments.

The algorithm could alternatively compute coverings from right to left. It is the same in reversal.

Starting from both ends may make the algorithm a bit more complicated (you have to work out the changes for yourself), On the other hand it may improve it somewhat as it can avoid having to recompute all segments up to the right end in pathological cases of incremental recomputation: you are sure an incremental update will not exceed half the collection of points ( actually it is not exactly half, depending on how the "meeting point in the middle" is chosen). But I guess it is a minor improvement. You might be even more subtle in choosing the "middle place" and in possibly changing it when you move your points, to account for changes of the algorithm behavior according to point density. But this is marginal and requires a bit of analysis.

Note: the above works for addition and removal of points, without necessarily keeping a constant number of points, provided it is allowed by the structures that I left unspecified and up to your own choice. The fact that the number of points remains constant in the statement of your problem could be an indication that a specific method is expected that would make use of that fact.

P.S. What do you mean by best approach ? What is the criterion.

# Answer
> 0 votes
You can cunstruct a max heap and a min heap. With the bottom up approach you can cunstruct it in O(n) time. For each point also keep maintaining a HashMap which stores its index. Since these are points they should not overlap (as I take them to)

This Can be done in O(n) time.

Now for each update query

All you have to do is get the element at index i from the HashMap. then delete it from both the heaps. O(log n). Also delete the key corresponding to this element from the HashMap. Now add the value (newVal, i) to the HashMap. O(1) for both delete and add. Now add the new point to both the heaps. O(log n).

And your answer is always the ceil of (top of max heap-top of min heap)/Length of segment. O(1)

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


title: Language independent software libraries

text:
# Question
Title: Language independent software libraries
When trying to decide on the choice of a programming language for a specific task, people will often tell me: "use this language because it has the best library for the type of problems you are addressing".

I would rather choose my language for its intrinsic qualities as a programming medium. That implies that libraries should be more universally usable.

What work has there been to create programming libraries that could be programmed and used in different languages, being mechanically adapted from one to the other on the basis of a standardized interface language/formalism (or any other mean)? How succesful has it been?

For example, I found one system that claims to do that : Microsoft's .NET Framework. They say it is based on a Common Language Specification (CLS) which is defined in the ECMA-335 Standard: Common Language Infrastructure.

Are there others? What about free-software frameworks?

Pointers to relevant papers or web sites are an answer. A survey would be best.

**Note** (June 7, 2013): this question is more controversial than is visible. However, I cannot fathom the nature of the controversy. Some people support the question and/or make cogent comments. But the people who seem unhappy about it just downvote without a word of explanation. I am sure they have a good reason to do so. But it would better help our understanding of the issues, or possibly of the lack of issues, if they were a little more explicit as to what irks them.

# Answer
### Java Bytecode

Similar to Microsoft's CLS, the Java Bytecode that the Java virtual machine executes gives you the (theoretical) possibility of using libraries from one JVM-targeting language with another JVM-targeting language. For example, Java libraries can be used in Scala, which IMO is a much better language than Java itself. Libraries written in Scala could be used in Clojure, or in Jython, or in one of these languages.

However, although interoperability is theoretically possible because of the common byte code to which all these languages compile, it is said (my personal experience is fairly limited) to sometimes be complicated to actually get it working.

Another, in the context of your question probably equally big drawback is, that using libraries from other languages often forces you to program in that languages style - and consequently "rip" you out of the style of the language you are actually programming in. For example, due to the lack of closures/anonymous functions and higher-order functions, Java libraries often don't have "nice" interfaces in the functional programming sense. Scala libraries, on the other hand, are usually written in a functional way.

### Multi-platform languages

Another way of addressing your problem are multi-platform languages such as Haxe.

> Haxe can be compiled to all popular programming platforms with its fast compiler – JavaScript, Flash, NekoVM, PHP, C++, C# and Java (soon).

To be fair, I don't have any experience with Haxe, so all I can do is conjecture. That said, I see this approach as a double-edged sword. On the one hand, it allows you to implement libraries only once and then compile them to C++, PHP, etc., and use them from their. On the other hand, if you write a client or a library depending on other libraries in Haxe, you are probably limited to Haxe libraries, and, for example, cannot use the highly appraised C++ library Boost.

A similar, although assumably less powerful approach is followed by Apache Thrift.

> Apache Thrift allows you to define data types and service interfaces in a simple definition file. Taking that file as input, the compiler generates code to be used to easily build RPC clients and servers that communicate seamlessly across programming languages. Instead of writing a load of boilerplate code to serialize and transport your objects and invoke remote methods, you can get right down to business.

### General worries

I assume that the "out of style" problem mentioned in the context of JVM-targeting languages is actually more general and probably something that makes it difficult to truly achieve what you want. If you specify interfaces arbitrarily general, it is likely that they feel out of place when used in any concrete programming language.

A second problem related to interfaces is which data structures to use as input/output data structures. For example, which data structures should a language-independent sorting library accept and return - arrays, sequences, lists, vectors, streams? And how are these mapped from/to data structures that actually exist in a given concrete language?

Another general problem I can see is performance. A library that is implemented in one language and cross-compiled into another is probably of poorer performance than one that is directly implemented in that language - which is not automatically a problem, but can definitely sometimes be one.
> 5 votes

---
Tags: programming-languages, formal-methods, typing
---


# Question
Title: Efficient data structures for building a fast spell checker
I'm trying to write a spell-checker which should work with a pretty large dictionary. I really want an efficient way to index my dictionary data to be used using a Damerau-Levenshtein distance to determine which words are closest to the misspelled word.

I'm looking for a data structure who would give me the best compromise between space complexity and runtime complexity.

Based on what I found on the internet, I have a few leads regarding what type of data structure to use:

## Trie

This is my first thought and looks pretty easy to implement and should provide fast lookup/insertion. Approximate search using Damerau-Levenshtein should be simple to implement here as well. But it doesn't look very efficient in terms of space complexity since you most likely have a lot of overhead with pointers storage.

## Patricia Trie

This seems to consume less space than a regular Trie since you're basically avoiding the cost of storing the pointers, but I'm a bit worried about data fragmentation in case of very large dictionaries like what I have.

## Suffix Tree

I'm not sure about this one, it seems like some people do find it useful in text mining, but I'm not really sure what it would give in terms of performance for a spell checker.

## Ternary Search Tree

These look pretty nice and in terms of complexity should be close (better?) to Patricia Tries, but I'm not sure regarding fragmentation if it would be better of worse than Patricia Tries.

## Burst Tree

This seems kind of hybrid and I'm not sure what advantage it would have over Tries and the like, but I've read several times that it's very efficient for text mining.

---

I would like to get some feedback as to which data structure would be best to use in this context and what makes it better than the other ones. If I'm missing some data structures who would be even more appropriate for a spell-checker, I'm very interested as well.

# Answer
I've encountered same problem, but took different approach. You can construct some kind of "hash" function, which will for similar word give same or near number.

Problem is, that function which will give "good" result for words with inserting/removing, will give "bad" for transition, and vice versa. Example: map letters to numbers, similar letter to adjacent numbers, and just sum them for every letter in word. Then create hash-tables with sets for each key and find intersection for word.

May be some results can be achieved if we look at "space" оf words. X for changing letter, Y for adding/removing, Z for transition, or something like that.

However this is only abstract ideas, I haven't enough time to implement them.
> 4 votes

# Answer
You may want to use a metric tree for fast research, if brute force is not possible (always try brut force). Finding your neighbours will be possible in $\mathcal O(\log (n))$, but the constant in $\mathcal O$ may be big. You seem to have millions of strings, so it may be a good trade-off.

Do not store the strings in the metric tree. Just store an index, and store the strings in a Patricia tree.

I am not sure which tree you should use. It will depend on your data and your requirements (do you need fast insert ?). Update your question if you find that one tree is more efficient than the others.

You may also look at specialized tools, like lucene.
> 4 votes

---
Tags: data-structures, strings, string-metrics
---


# Question
Title: Doubts on Definition of Indistinguishable Encryption in the Textbook
In the classic crypto textbook "Introduction to Modern Cryptography" by Jonathan Katz and Yehuda Lindell, there is a definition for indistinguishable encryption in the presence of an eavesdropper as such that for every probabilistic polynomial time adversary A there is a negligible function negl(n) such that

$\Pr\[PrivK\_{A,\Pi}=1\] \leq negl(n)$

where PrivK is the indistinguishability experiment and for the purpose of this question we only need to know that the experiment outcome is 1 iff the adversary makes the correct guess.

My doubts are as follows. Consider a sequence of probabilistic polynomial time adversaries $\\{A\_i\\}\_{i\>=1}$ whose advantage in the indistinguishability experiment is bounded by the following sequence of negligible functions

$\Pr\[PrivK\_{A,\Pi}=1\] \leq negl\_i(n) = \frac{1}{(1+1/i)^n}$

Clearly it is necessary for the above conditions to hold for a indistinguishable encryption. But is it a correct model/condition for real-world applications? For example, in practice we typically choose a sufficiently large n and set up some encryption scheme. However, there is the always some adversary $A\_i$ that wins the experiment with probability close to one. So what's wrong?

# Answer
Depends on how different your algorithms are. If you can compute $A\_i$ from $i$ in polynomial time, then $A'$ with $A'(n) = A\_n(n)$ is a polynomial time adversary too and violates the assumption (as it has non-negligible success probability). This would make your series of $A\_i$ *uniform* and is one usual class of adversaries to consider.

If you'd like your crypto system to be secure against *any* such series of polynomial bounded adversaries you have to consider *non-uniform* adversaries (at least non-uniform in polynomial time), by e.g. defining a single adversary as a series of (randomized) circuits with polynomial size.
> 2 votes

---
Tags: cryptography
---


# Question
Title: Show the problem of a machine visiting infinitely many tape cells on some input is undecidable
I am attempting to prove the following problem is undecidable. Given a Turing machine $M$ and input $x$, does $M$ visit infinitely many tape cells on input $x$?

I am considering a reduction from the halting problem. Is this the right approach?

# Answer
> 3 votes
Based on my comments, I might as well make this an answer, and let the community decide whether it's right or not.

Suppose you could decide whether a TM visits an infinite number of cells on an input. Here's how to solve the Halting problem given this information:

```
Halts(TM, input)
1. if the TM visits an infinite number of cells for the input then return false
2. configurations = {}
3. while(true)
4.     configurations.add(non-blank tape area, TM head position, state)
5.     let the TM execute one step
6.     if state is halt accept or halt reject, return true
7.     if configurations.contains(non-blank tape area, TM head position, state) then return false
8. loop

```

This works because, if the TM doesn't visit an infinite number of cells, it visits some finite number of cells, $n$. The number of distinct configurations is therefore $|\Sigma|^n \times n \times |Q|$, and `configurations.size()` will never be bigger than this. By the pigeonhole principle, we must satisfy at least condition #7 in a finite number of moves. If none of the reached configurations enters a halting state, we never will; so we have to halt before we see the same configuration twice.

# Answer
> 0 votes
Yes this approach is correct. Try to visit a new blank cell between two computation steps by e.g. using some markers.

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


# Question
Title: why are deterministic PDAs not closed under concatenation?
I can understand that they are not closed under concatenation because without non determinism, PDA cannot decide whether to loop in the first PDA or jump to the next one. But can someone prove this with an example. Also prove that the resulting language cannot be accepted by DPDA

# Answer
Pick the languages:

$L\_1 = \\{a^ib^jc^k | i \neq j \\}$ and $L\_2 = \\{a^ib^jc^k | j \neq k\\}$; both are DCFL and $L\_3 = 0L\_1 \cup L\_2$ is DCFL, too.

$L\_0 = 0^\*$ is DCFL (regular)

But $L\_{conc} = L\_0 \cdot L\_3 = 0^\* L\_3$ is not DCFL.

**Proof:** Suppose that $L\_{conc}$ (which is the concatenation of two DCFLs) is DCFL.

If we intersect $L\_{conc}$ with the regular language $0a^\*b^\*c^\*$, we should get a DCFL language:

$L\_{conc} \cap \\{0a^\*b^\*c^\*\\}$ = $0L\_1 \cup 0L\_2$. suppose $0L\_1 \cup 0L\_2$ is a DCFL, so $L\_1 \cup L\_2$ should be a DCFL, too but:

$L\_1 \cup L\_2 = \overline{\overline{L\_1} \cap \overline{L\_2}} = \overline{\\{a^ib^ic^i\\}}$ which is not DCFL $\Rightarrow$ contradiction.
> 10 votes

# Answer
Explain how, given a PDA for a L1 and a PDA for L2, you can construct a PDA for the concatenation L1L2.?
Answer: The basic answer is to take the accept state for L1, and make it
the start state for L2. However – if L1 leaves symbols on the stack
(other than delta), we might have to pop them. It is not required the stack be empty at accept. So we need a non-deterministic pop to clear
out the stack. Solution on right
> -2 votes

---
Tags: automata, pushdown-automata
---


title: What is a Turing Machine in class coNP

text:
# Question
Title: What is a Turing Machine in class coNP
On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial\_hierarchy

it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B"

What is a "Turing machine in class A" for classes P, NP, and coNP?

I'm guessing a Turing machine in P is a deterministic Turing machine that can only run for polynomial time in the size of its input

and that a Turing machine in NP is a nondeterministic Turing machine that can only run for polynomial time in the size of its input

But I have no clue what is a Turing machine in class coNP ?

# Answer
You *can* define co-NP as: $$\\{L\mid \exists\text{polyn.time } \text{NTM }M: L=\\{w\mid \text{all computations paths of }M(w) \text{ accept}\\} \\}$$ This directly corresponds to the definition of the $\forall^p$ operator in the next section of the mentioned article. However, nearly all definitions of NP rely on TMs or some other concept of algorithms which usually can be equipped with oracles.

However you very well spotted a problem of the oracle definition for complexity classes: $\mathcal A^{\mathcal B}$ implicitly assumes that $\mathcal A$ can be defined using Turing machines, while it may be any set of languages. Sometimes this is avoided by defining $\mathcal A$ as a set of Turing machines or algorithms instead (usually denoted by the same name as the complexity class those algorithms define).
> 3 votes

# Answer
The easiest way (for me) to understand co-NP is as the class of problems where certificates for "No" answers can be quickly verified (i.e. certificates of non-membership).

So if we look at NP as a class of nondeterministic Turing Machines which quickly (in polynomial time) determine that their input satisfies some property $\Pi$, co-NP is the class of nondeterministic Turing Machines that quickly determine that their input does not satisfy $\Pi$ (or equivalently satisfies $\neg\Pi$).
> 3 votes

---
Tags: turing-machines, decision-problem, np, polynomial-time
---


# Question
Title: How to prove formally that grammar isn't LR(1)
I want to prove that grammar $$ \begin{cases} S'\rightarrow S\\ S\rightarrow aSb ~|~ A\\ A\rightarrow bA~|~b \end{cases} $$ isn't $LR(1)$. I've constructed parser table and got Shift-Reduce conflict.

I want to prove that without parser table, using another $LR(1)$ definition.

Here's definition: Grammar is $LR(1)$, if from

1. $S' \Rightarrow^\*\_r uAw \Rightarrow\_r uvw$
2. $S' \Rightarrow^\*\_r zBx \Rightarrow\_r uvy$
3. $FIRST(w) = FIRST(y)$

$\Rightarrow uAy=zBx.$

So how can prove that?

# Answer
$$S'\Rightarrow^\*\underbrace{ab}\_uA\underbrace{b}\_w\Rightarrow \underbrace{ab}\_u\underbrace{b}\_v\underbrace{b}\_w$$

$$S'\Rightarrow^\*\underbrace{abbbb}\_zA\underbrace{b}\_x\Rightarrow \underbrace{ab}\_u\underbrace{b}\_v\underbrace{bbbb}\_y$$

$$FIRST(w)=FIRST(y)=b$$ But: $$abAbbbb=uAy\neq zBx=abbbbAb$$
> 2 votes

---
Tags: formal-grammars, parsers
---


# Question
Title: Finding a winning strategy for toads and frogs
Recently I got interested in a game called Toads and Frogs and I'm trying my best to come up with some software which would be able to beat an average (i.e. not knowing the strategy) human though I'm struggling with the strategy.

I read on it everything I could google out but turns out there's not that much to read about it as one may think - the most helpful thing I've found was probably an analysis by Erickson though it concentrates more on evaluating each position rather than some algorithm which would have to decide how to move a toad or a frog given a particular board as input. Same goes for "Winning Ways", where they evaluate a bunch of positions but don't give you too much insight on how to optimally play your game

The best playthrough strategy I could come up with is evaluating the value of the current position (using "Winning Ways" and Erickson's tricks), evaluating the values of all the positions we can go to with our toads/frogs in a given moment and then performing a move which leads to the lowest value of the board so that our opponent has the worst moves to choose from.

Is there anything better? Or if all the "good" strategies are very hard (as I said, I'm just starting out with my game theory interest), what's the best one that even someone with my experience could utilize? :)

# Answer
> 9 votes
Ultimately, unless you can prove something *very* interesting, you're stuck with exponential backtracking. For at least one natural encoding of positions, Toads and Frogs is NP-hard.

Jesse Hull observed that the position $T^n\Box TFT^m \Box TF$ has the game value $\\{m+n-1\mid \\{ n\mid 2 \\}\\}$, which means

* If $T$ moves first, $T$ gets $m+n-1$ free moves.
* If $F$ moves first and then $T$, then $T$ gets $n$ free moves.
* If $F$ moves twice, $T$ gets $2$ free moves.

By combining this position with positions of the form $T\Box^x$ and $\Box^y F$, we can set up a position whose value is $\\{a\mid\\{b\mid c\\}\\}$ for any integers $a,b,c$.

Yedwab and Meows proved that determining which player wins a sum of games with values $\\{a\_i\mid\\{b\_i\mid c\_i\\}\\}$ is NP-hard. A sum of games is a set of games that are being played simultaneously; each player can choose which game to play in on their turn; and the first player unable to move at all wins. Toads and Frogs positions often decompose into sums; for example, a position that contains $TTFF$ is equivalent to the sum of the pieces to the left and the pieces to the right.

These two results imply that playing Toads and Frogs optimally is NP-hard **if positions are run-length encoded**. That is, any string of $n$ frogs should be encoded using only $O(\log n)$ bits, encoding the integer $n$ in binary, *not* using $O(1)$ bits per frog.

It is possible, although I think *very* unlikely, that an optimal move in Toads and Frogs can be computed in polynomial time if the input position is encoded as a simple string over the alphabet $\\{T, \Box, F\\}$. (Yedwab's NP-hardness proof is a reduction from PARTITION, which is only weakly NP-hard.)

---
Tags: algorithms, combinatorics, game-theory
---


# Question
Title: For complexity classes A and B, what does $A^B$ mean?
What does $A^B$ mean where A and B are complexity classes?

The "Polynomial Hierarchy" page says:

$A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B

In that case what is a Turing machine in class A?

(besides just a machine of some sort that can solve problems in A, because that doesn't give any insight as to what it means to augment such a machine with an oracle)

The motivation for this question was: What is a Turing Machine in class coNP.

# Answer
> 3 votes
An *oracle* is a way for a Turing Machine to ask a question and get it answered immediately, "magically". The way we usually model it is that the Turing Machine can write down the question on a special, extra tape, and then (say) the tape is erased and the answer immediately written on it.

More specifically, we usually suppose that the oracle is for a particular *language*, so we write a string on the tape, followed by some special "end-of-string" symbol; then, the formula disappears and is replaced by either "YES" or "NO".

For a concrete example, suppose our Turing Machine has an oracle for SAT. Then it can write a formula on the string and immediately find out if it's satisfiable or not.

Notice that, since SAT is NP-Complete, a TM with a SAT oracle can decide any language in NP in polynomial time: Just reduce the input to a SAT formula, and then ask the oracle about this SAT formula.

So we might write $P^{NP}$ for the set of languages that can be decided in polynomial time by a TM with an oracle for SAT.

---
Tags: turing-machines, complexity-classes, notation, oracle-machines, relativization
---


title: Self-Study of Computer Science

text:
# Question
Title: Self-Study of Computer Science
I am a 16 year old male who has recently been gifted a big encyclopedia on computer science by a friend of mine. I am usually not that interested in computers and technology, but computer science has started to fascinate me. I do however intend to study Physics and/or Mathematics and not CS, so my question is, would it be useful to conduct a self-study of computer science? I'm not of course going for the level of a BSc but just the basics of CS (it is an encyclopedia with ~600 pages).

# Answer
I think that learning about computer science certainly can be an advantage. Here are a number of (related) skills computer science has to offer.

1. **Programming** – knowing how to program is a useful skill for any discipline. Statisticians and sociologists, geographers and engineers, and so on, often find themselves needing to program. Following a CS degree should teach you to program properly.
2. **Modelling** – one of the key things computer scientists do is modelling the world. True, physicists, biologies and sociologists do too, but the kinds of models they are different. Knowing about the kinds of models computer scientists build can often help modelling in other disciplines. Even better, computer science models are generally executable (see point 1).
3. **Abstraction** – computer science is all about abstraction, ignoring irrelevant details to bring out the core of a problem. When modelling a programming language, not every single detail is modelled. One can abstract away from almost all details and study the concurrency model in isolation or just the classes in an object-oriented language. This kind of abstraction is less common in other sciences (I claim), but they are crucial for understanding phenomena computer scientists are interested in. I'm sure that other fields could benefit from some abstraction.

This is probably best summed up in an article about **Computational thinking** by Jeannette Wing.
> 15 votes

# Answer
I would say that anyone in a Science/Engineering track should have at least some CS. Familiarity with at least one programming language, data structures, and basic knowledge of algorithms will come in handy more than you think...

I never thought it would matter much, but now I wish I had tackled these things earlier in my career.

Not sure about a good "intro to programming book" but this was a decent intro to algorithms book.

Not sure about the suggestion to take "real" courses either. Be careful and ask around about the teacher/work load. I was not impressed by the ones I took and feel like I was better off on my own in some respects. Don't feel bound to the prerequisites, talk to the advisers and get placed in the classes that will help you the most.
> 4 votes

# Answer
Computers are a great tool for physicists, say you want to run a simulation about a physical phenomenon it would be useful to know the fastest algorithm avaliable, if it can be computed in a reasonable amount of time, etc.

I'm a software engineer and love computer science, it's good to know what problems computers can solve as well.
> 1 votes

# Answer
If you have been studying physics or maths , studying computer science wont be a problem for you , and it is always good to get some knowledge from a good source. You are also right in your own sense if you dont have to pursue a degree in computer science why you should study that , but you can think it in other way also , inspite of spending your time here and there during your vacations you can learn computer science , as of today you dont want to pursue carrier in computer science , but tomarrow your opinion may change with time. Even if you dont change your mind a knowledge earned is never wasted. Just try with introduction part of few chapters you will be convinced to read more and then you can move further.
> 0 votes

---
Tags: reference-request, education
---


# Question
Title: Evolutionary algorithm for the Physical Travelling Salesman Problem
I want to solve the Physical Travelling Salesman Problem using an evolutionary algorithm.

The objective of the PTSP is to visit the maximum number of waypoints of the map in the minimum number of time steps. The map takes the form of a two-dimensional board, where ten waypoints are scattered around and multiple obstacles are present.

Now, I have a way to run random games and create "population" — a list of waypoints in the order we visit them. I need some idea how to do the crossover. I mean, how to create the next generation. I saw ideas, but they take in account that each gene contains *all* the waypoints on the map. (Take a random part from parent1 and take the waypoints that do not appear in parent1 from parent2 in the order they appear in parent2). What to do in case a gene contains just part of the waypoints?

# Answer
> 2 votes
Have a look at this survey on crossover operators for TSP

It gives you the history of development on this area as well.

List of operators covered:

* Partially Mapped Crossover (PMX) \[Goldberg, 1985\]
* Order Crossover (OX) \[Davis, 1985\]
* Edge Crossover (EX) \[Whitley, 1989\]
* Subtour Exchange Crossover (SXX) \[Yamamura, 1992\]
* Edge Exchange Crossover (EXX) \[Maekawa, 1996\]
* Edge Assembly Crossover (EAX) \[Nagata, 1997\]
* Partition Crossover (PX) \[Whitley, 2009\]

---
Tags: genetic-algorithms, traveling-salesman
---


title: How not to solve P=NP?

text:
# Question
Title: How not to solve P=NP?
There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction.

I know that there are approaches that have been proven to not work, and there are probably more that have a history of failing. There also seem to be so-called *barriers* that many proof attemps fail to overcome.

We want to avoid investigating into dead-ends, so what are they?

# Answer
> 82 votes
I'd say the most well known barriers to solving $P=NP$ are

1. Relativization (as mentioned by Ran G.)
2. Natural Proofs - under certain cryptographic assumptions, Rudich and Razborov proved that we cannot prove $P\neq NP$ using a class of proofs called natural proofs.
3. Algebrization - by Scott Aaronson and Avi Wigderson. They prove that proofs that algebrize cannot separate $P$ and $NP$

Another one I'm familiar with is the result that no LP formulation can solve TSP (It was proved by Yannakakis for symmetric LPs and very recently extended to general LPs). Here is a blog post discussing the result.

# Answer
> 61 votes
Note: I haven't checked the answer carefully yet and there are missing parts to be written, consider it a first draft.

This answer is meant mainly for people who are not researchers in complexity theory or related fields. If you are a complexity theorist and have read the answer please let me know if you notice any issue or have an idea about to improve the answer.

### Where you can find claimed solutions of P vs. NP

* There is The P-versus-NP page which has a list of such claims.
* Articles claiming to resolve the question are regularly posted on arXiv.

### Other lists of how not to solve P vs. NP

Lance Fortnow, So You Think You Settled P verus NP, 2009

Scott Aaronson, Eight Signs A Claimed P≠NP Proof Is Wrong, 2010

Polymath page for Deolalikar's paper, where the further readings section has nice list of references about the problem.

---

### How not to approach P vs. NP

Let me discuss "how not to *approach* P vs. NP" not in the sense of ideas that will not work but in a more general sense. P vs. NP is a easy to state problem (see also my answer here):

> **NP = P :** For every decision problem with a polynomial time verifier algorithm there is an polynomial time algorithm.

or equivalently

> There is a polynomial time algorithm for SAT.
> SAT can be replace with any other NP-complete problem.

.

Often people oversimplify and overphilosophize the problem and exaggerate the practical importance of the problem (as stated above). Such statements are often meant to give intuition, but they are not in any way a replacement for the actual mathematical statement of the problem.

### Theoretical efficiency is *not* the same as feasibility in practice.

Let me first with exaggerated practical consequences.

**I.** It is possible that P=NP but it does not help for any problem in practice!

Say for example that SAT is in P but the fastest algorithm for its running time is $2^{2^{64}} n^{65536} + 2^{2^{128}}$. This algorithm is of no practical use.

**II.** It is possible that P$\neq$NP and we can solve NP-complete problems *efficiently*.

Say for example that SAT is not in P but has an algorithm with running time $n^{\lg^\*\lg^\* n}$.

To give an input that would make $\lg^\* n \> 6$ you have to use more electrons that there are thought to be in universe. So the exponent is essentially $2$.

The main point here is that P is an abstract simple model of efficient computation, worst-case complexity is an abstract simple model of estimating the cost of a computation, etc. All of these are abstractions, but no one in practice would consider an algorithm like the one in (I) above as an efficient algorithm really. P is a nice abstract model, it has nice properties, it makes technical issues easy, and it is a useful one. However like all mathematical abstraction it hides details that in practice we may care about. There are various more refined models but the more complicated the model becomes the less nice it would be to argue about.

What people care about in practice is to compute *an* answer to the problem for instances that *they care about* using *reasonable* amount of resources. There are task dependent and should be taken into consideration.

Trying to find better algorithms for practical instances of NP-hard problems is an interesting and worthy endeavor. There are SAT-solver heuristic algorithms that are used in the industry and can solve practical instances of SAT with millions of variables. There is even an International SAT Competition.

(But there are also small concrete instances that all these algorithms fail and fail quite badly, we can actually prove that all state of art modern SAT-solvers take exponential time to solve simple instances like propositional Pigeonhole Principle.)

Keep in mind that *correctness and running time of programs cannot be obtained just from running the program on instances*. It does not matter how many instance you try, no amount is sufficient. There are infinitely many possible inputs and you have to show correctness and efficiency (i.e. running time is polynomial) of the program for all of them. In short, you need mathematical proof of correctness and efficiency. If you do not know what is a mathematical proof then you should first learn some basic mathematics (read a textbook discrete math/combinatorics/graph theory, these are good topic to learn about what is considered a mathematical proof).

Also be careful about other claims about P vs. NP and the consequence of its answers. Such claims are often based on similar simplifications.

### Complexity theorists do not really care about an answer to P vs. NP!

I exaggerated a bit. Of course we do care about an answer to P vs. NP. But we care about it in a context. P vs. NP is our flagship problem but it is not the ultimate goal. It is an easy to state problem, it involves many fundamental ideas, it is useful for explaining the kind of questions we are interested in to people who are not familiar with the topic. But we do not seek a one bit Yes/No answer to the question.

We seek **a better understanding of the nature of efficient computation**. We believe that resolving the question will come with such understanding and that is the real reason we care about it. It is part of a huge body of research. If you want to have a taste of what we do have look at a good complexity theory textbook, e.g. Arora and Barak's "Complexity Theory: A Modern Approach" (draft version).

Let us assume that someone comes with an encrypted completely formal proof of P$\neq$NP and we can verify its correctness to a very high degree of confidence by selecting and decrypting a few bits of the proof (see Zero-Knowledge Proof and PCP theorem). So we can verify the claim with probability of error less than a meteor hitting our house, we are quite sure the proof is correct and P=NP, but we do not know the proof. It will not create much satisfying or exciting for us. The formal proof itself will not also be that satisfying. What we seek is not a formal proof, what we seek is understanding.

In short, from a complexity theorist's perspective

> P vs. NP is not a puzzle with a Yes/No answer. We seek an answer to P vs. NP because we think it will come a better understanding of the nature of efficient computation. An answer without a major advancement in our understanding is not very interesting.

There has been too many occasions that non-experts have claimed solutions for P vs. NP, and those claims typically suffer from issues that they would not have made if they just read a standard textbook on complexity theory.

### Common problems P=NP

The claims of P=NP seem to be more common. I think the following is the most common type. Someone has an idea and writes a program and tests it on a few instances and thinks it is polynomial time and correctly solves an NP-complete problem. As I explained above no amount of testing will show P=NP. **P=NP needs a mathematical proof**, not just a program that *seems* to solve an NP-complete problem in polynomial time.

These attempts typically suffer from one of the two issues:

I. the algorithm is not really polynomial time.

II. the algorithm does not solve all instances correctly.

### Signs that a P$\neq$NP argument is not correct

\[to be written\]

### How to check that your algorithm does *not* really work

You cannot show that your algorithm works correctly by testing. But you can show it does not work correctly by testing! So here is how you can make sure that your algorithm is not correct if you are willing to do some work.

First, write a program to convert instances of SAT (in the standard CNF format) to the NP-hard problem that you are solving. SAT is one of the most studied NP-hard problems and reductions from other problems to SAT is typically easy. Second, take the examples that the state of art SAT-solvers struggle with (e.g. take the examples from SAT competition) and feed them to your algorithm and see how your algorithm performs. Try known hard instances like propositional Pigeonhole Principle (and don't cheat by hard-coding them as special cases), cryptographic instances (like RSA Factoring Challenges), random k-SAT instances near the threshold, etc.

Similarly you can check that your algorithm is not efficient. E.g. if you think your algorithm's running time is not $10 n^2$ but it is taking days to solve an instance of say size 1000. Fix the polynomial worst-case running-time upper bound that you think your algorithm has. Take the instances and estimate the time your algorithm will take to solve them and check if matches your estimates.

### How to check your algorithmic P=NP *idea* cannot work

If you do these you will be pretty sure that your algorithm does not work (if it works better than the state of the art SAT-solvers then compete in the next competition and lots of people would be interested in studying your algorithm and ideas).

Now you know it does not really work but that is not enough. You want to know why,

> is the reason my algorithm does not work a small issue that can be fixed or is there a fundamental reason why it cannot work?

Sometimes the problem with the algorithm is simple and one can identify what was wrong conceptually. The best outcome is that you understand the reason your idea cannot work. Often it is not the case, your idea does not work but you cannot figure out why. In that case keep in mind:

> understanding why some idea cannot work can be more difficult that solving P vs. NP!

If you can formalize your idea enough you might be able to prove a limitations of particular ideas (e.g. there are results that say particular formalizations of greedy algorithm cannot solve NP-complete problems). However, it is even more difficult, and you do not have much chance if you have not read a standard complexity theory textbook.

Sometime there is not even a clear conceptual idea why the algorithm should work, i.e. it is based on some not well-understood *heuristics*. If you do not have a clear conceptual idea of why your algorithm should work then you might not have much chance in understanding why it does not!

### Common problems with P$\neq$NP claims

Although most experts think P$\neq$NP is more likely than P=NP, such claims seems to be less common. The reason is that proving lower-bounds seems to be a harder task than designing algorithms (but often proving lower-bounds and upper-bounds are intrinsically related).

Issue 1: the author does not know the definition of P and NP, or even worse does not understand what is a mathematical proof. Because the author lacks basic mathematical training he does not understand when he is told what he is presenting is not a proof (e.g. the steps do not follow from previous ones).

Issue 2: the author confuses "we don't know how" with "mathematical impossibility". For example they make various unjustified assumptions and when asked "why this statement is true?" they reply "how can it be false?". One common one is to assume that any program solving the problem has to go throw particular steps, e.g. it has to compute particular intermediate values, because he cannot think of an alternative way of solving the problem.

\[to be completed\]

### Signs that a P$\neq$NP argument is not correct

\[to be written\]

### How to check your P$\neq$NP *idea* cannot work

If a claim does not suffer from these basic issues then rejecting it becomes more difficult. On the first level one can find an incorrect step in the argument. The typical response from the author is that I can fix it and this back and forth can go on. Similar to P=NP solutions it is often a very difficult to find a fundamental issue with an idea that can show it cannot work, particularly when the idea itself is informal.

In the best case, if we can formalizes the idea and identify the obstacle that shows the idea cannot work we have proven a new barrier result (this is how attempts to prove P$\neq$NP using circuit lower-bounds lead to the Natural Proofs barrier).

# Answer
> 36 votes
Maybe the most common technique that cannot be used is relativization, that is, having a TM with oracle access.

The impossibility follows from a paper by Theodore Baker, John Gill, Robert Solovay who show the existence of two oracles (languages), $A$ and $B$ such that $\text{P}^A = \text{NP}^A$ and $\text{P}^B \ne \text{NP}^B$.

Thus, if some proof for, say, $\text{P}\ne \text{NP}$ can be relativized, this would mean that for all oracles $O$, $\text{P}^O \ne \text{NP}^O$ which contradicts the existence of $A$.

Specifically, this means *diagonalization* cannot be used to prove $\text{P} \stackrel{?}{=} \text{NP}$ as those proofs can be relativized, see e.g. these lecture notes.

# Answer
> 10 votes
I'd suggest reading this blog post by Lance Fortnow:

> 1. So You Think You Settled P verus NP You are wrong. Figure it out. Sometimes you can still salvage something interesting out of your flawed proof.
> 2. You believe the proof is correct. Your belief is incorrect. Go back to step 1.
> 3. Are you making any assumptions or shortcuts, even seemingly small and obvious ones? Are you using words like "clearly", "obviously", "easy to see", "should", "must" or "probably"? You are claiming to settle perhaps the most important question in all of mathematics. You don't get to make assumptions. Go back to step 1.
> 4. Do you really understand the P versus NP problem? To show P≠NP you need to find a language L in NP such that for every k and every machine M running in time $n^k$ (n = input length), M fails to properly compute L. L is a set of strings. Nothing else. L cannot depend on M or k. M can be any program that processes strings of bits. M may act completely differently than one would expect from the way you defined L. Go back to step 1.
> 5. You submit your paper to an on-line archive. Maybe some people tell you what is missing or wrong in your paper. This should cause you to go to step 1. But instead you make a few meaningless changes to your paper and repost.
> 6. Eventually people ignore your paper. You wonder why you aren't getting fame and fortune.
> 7. You submit your paper to a journal.
> 8. The paper is rejected. If you are smart you would go back to step 1. But if you were smart you would never have gotten to step 7.
> 9. You complain to the editor that either the editor doesn't understand the proof or that it is easily fixed. You are shocked a respectable editor or journal would treat your paper this way.
> 10. You resubmit the paper, appeal, try other journals all to no avail.
> 11. You are convinced "the establishment" is purposely suppressing your paper because our field would get far less interesting if we settle the P versus NP problem so we have to keep it open at all costs.
> 12. If I tell you otherwise would you believe me?

# Answer
> 2 votes
here is a somewhat obscure/deep/difficult/insider angle/reference/twist relating to approaches via circuits dating from the 1980s originally pointed out to me years ago by Luca Trevisan elsewhere in cyberspace, and also reiterated by Stasys Jukna, author of an excellent reference near to the subject, Boolean Function Complexity: Advances and Frontiers (Algorithms and Combinatorics, Vol. 27).

one can see an earlier trend in some of Razborov's thinking that eventually led to the Natural Proofs paper (so-called "naturalization"). ref \[273\] is very technical & difficult and does not seem to be cited, built on/expanded, or reiterated much by later papers/books although Natural Proofs could be seen as a later large generalization. the excerpt is from John E Savages excellent ref Models of Computation p457

> Having shown that monotone circuit complexity can lead to exponential lower bounds \[270\], Razborov \[271\] then cast doubt on the likelihood that this approach would lead to exponential non-monotone circuit size bounds by proving that the matching problem on bipartite graphs, a problem in P, has a super-polynomial monotone circuit size. Tardos \[324\] strengthened Razborov’s lower bound, deriving an exponential one. Later Razborov \[273\] demonstrated that the obvious generalization of the approximation method cannot yield better lower bounds than $\Omega(n^2)$ for Boolean functions on $n$ inputs realized by circuits over complete bases.

\[270\] A. A. Razborov, “Lower Bounds on the Monotone Complexity of Some Boolean Functions,”Dokl. Akad. Nauk SSSR (Soviet Math. Dokl.) 281 (1985), 798–801, (in Russian); English translation in Soviet Math. Dokl. 31 (1985), 354–357

\[271\] A. A. Razborov, “A Lower Bound on the Monotone Network Complexity of the Logical Permanent,” Mat. Zametki 37 (1985), 887–900, (in Russian); English translation in Math. Notes 37 (6) (1985), 485–493.

\[273\] A. A. Razborov, “On the Method of Approximations,” Proc. 21st Ann. ACM Symp. Theory of Computing (1989), 167–176.

---
Tags: complexity-theory, reference-request, history, p-vs-np, reference-question
---


# Question
Title: What the difference between the Fourier Transform of an image and an image histogram?
Consider this small picture of a sunflower, and its histogram:

> What would the Fourier transform of the first picture look like? Is there any relationship between the histogram and the Fourier transform?

# Answer
> 1 votes
This post is a copy from the top voted answer to the question What does the Fourier Transform mean in the context of images? The answer is math.sx user due to dls.

In sound processing, the Fourier Transform has a physically intuitive meaning. A sound or function $f : \[0,b\] \rightarrow \[-1,1\]$ can be represented as a trigonometric series. And each term of the series corresponds to a frequency which you perceive. Many effects (like filtering, reverb, etc.) have an interpretation in the frequency domain which is useful for analysis. Unfortunately, the physical interpretation isn't as simple when we start talking about images. But on the analytic usefulness transfers over.

If we're talking about grey-scale, then an image is simply a function $f : \[0,1\]^2 \rightarrow \[0,1\]$. It takes a point in the square $\[0,1\]\times\[0,1\]$ and produces a value between 0 and 1, the intensity. The Fourier Transform just says we can represent this function in the frequency domain using a countable basis of trigonometric functions. Say you want to blur an image; this corresponds to a low-pass filter in the frequency domain. The following link shows many examples of Fourier transforms of images, gives an explanation of the physical interpretation (which I don't claim to understand entirely) and shows examples of basic image processing. This website shows more illustrative examples.

Another very important use of (variants of) the 2d-Fourier transform is image compression. The Wikipedia page for the JPEG codec lists the basis functions used to represent images.

Finally, note that if you're talking about an RGB image you can represent the image using the Fourier transform on each color component.

---
Tags: image-processing, graphics, fourier-transform
---