Advice for Graduate School in Computer Science I am looking for some advice and feedback.

Background: I am an undergraduate mathematics student, with an interest in theoretical computer science (computational complexity, graph theory, combinatorics). I want to pursue a PhD in Computer Science and focus on theory.

My background is in mathematically intensive areas of computer science, but I lack a more applied background in computer science. Specifically I need to complete courses in Programming, Algorithms, Operating Systems, & Databases as prerequisite work for a PhD program. I cannot fit these courses in before graduation. To remedy this I plan to enter the work force and complete a MS part time (so I can pay for the MS), then upon completion of the MS degree enter a full time PhD program.

Question: Would I be at a disadvantage by completing a MS degree part time, prior to entering a PhD program, as opposed to CS students that enter a PhD program immediately upon the completion of their undergraduate degree? The position I work in would be related to CS and would give me transferable skills to a CS program & may help lead me to better focused research. I am just hoping this path does not put me at any kind of disadvantage (in terms of acceptance to a PhD program). I am interested in doing the MS thesis track, and realize that it may take me a little longer to complete the MS degree (since it would be part time). Upon completion of the MS, as stated, I would enter a full time PhD program.

I am just looking for some feedback and advice. Thanks for your help!

I want to disagree slightly with Dave Clarke and Lev Reyzin.  At least in my department, PhD admission standards for students with MS degrees are higher than for students with only bachelor's degrees.  Additional experience can be a disadvantage, if it isn't enough additional experience.

All else being equal, my department expects any applicant with an MS to have a publication, or at least a publishable result, before we will consider them for admission to the PhD program.  (And by "published", I mean in a reputable peer-reviewed web-accessible conference proceedings or journal, not just a master's thesis, internal technical report, student research conference, or The Inaccessible Chinese Journal of Computer Science.)  Working a full time job is unlikely to leave you enough time—or more importantly, enough mental energy—to do publishable research.

Of course, ceterus is never paribus.  We do soften the de facto publication requirement for  MS applicants who have switched major fields.  But then you're in the uncomfortable position of explaining a perceived weakness.  (On the other hand, I'm not sure switching from mathematics to theoretical computer science counts as "major".)

My advice is not to put your eggs in one basket.  First, talk to people you might work with in the programs you are interested in.  Let me emphasize the plurals here — talk to multiple people in multiple departments.  Second, in the absence of specific contradictory advice from target departments, apply to both MS and PhD programs.  (Some universities, or at least their web forms, stupidly make you pick one or the other, in which case you must talk directly to the admissions office of your target department.)  Sane PhD programs let incoming students from other fields take undergrad CS courses for remediation.


What does it mean for a language to have "order"? In calculus, a polynomial has order $n$ if it contains terms that raise the unknown to a power $n$.

I'm trying to figure out how this definition of "order" relates to the use of the same word when talking about formal languages.

We say a logic or language is "first order", "second order", or "higher order".  I know it is related to what kinds of states of expressible within that language,b ut what does this mean, fundamentally, and why is it called the "order" of the language?

My angle on a related distinction: http://chrisamaphone.livejournal.com/751991.html

The "order" of nth-order (including higher-order) logic refers to the level of things that can be quantified over. In first-order logic, the things quantified over are terms of some unrelated domain: "All men are mortal." In second order logic, you can quantify over first-order predicates: "All properties of men also hold of dragons." Higher-order logic is the generalization of this to all higher predicates, which I think is better understood in terms of system F-omega (equivalent to HOL), wherein you can form type operators (constructors of kind type -> type) which can be quantified over as well as types.

The relation to "order" in polynomials is better understood as an analogy pertaining to recursion (nth order polynomials include a term multiplied by itself n times) than anything more rigorous.


"Parity testing set" for disjoint pairs of sets I'd like a construction of the following description.  Let $V$ be a set of $n$ elements.  I'd like a collection $X$ of subsets of $V$ such that for any pair $(P,Q)$ of disjoint subsets of $V$, there is an element $S \in X$ such that $|S \cap P|$ and $|S \cap Q|$ are both odd.
Probabilistic arguments indicate that there exists solutions with $|X|=O(n)$, but I'd like an explicit design.  I'd also like to know the best possible constant factor in the size $|X|$.
It sounded basic enough that I thought it should be solved, or easily attackable, but I'm drawing a blank. Any pointers?

Recall that a distribution $Y$ over $\{0, 1\}^n$ is called $\epsilon$-biased if for every nonempty set $P \subseteq [n]$, we have
$$
\left|\mathbb{E}[\oplus_{i \in P} Y_i] - \frac{1}{2}\right| \leq \frac{\epsilon}{2}.
$$
In other words, an $\epsilon$-biased distribution is a primitive kind of pseudorandom generator: it fools parity functions with error $\epsilon/2$. I claim that an $\epsilon$-biased distribution automatically also fools functions of the form $\mathsf{AND} \circ \mathsf{PARITY}$. That is:
Claim: Let $f \colon \{0, 1\}^n \to \{0, 1\}$ be of the form $f(x) = \wedge_{i = 1}^m \bigoplus_{j \in P_i} x_j$, where $P_1, \dots, P_m \subseteq [n]$. Let $Y$ be $\epsilon$-biased and let $U$ be uniform random over $\{0, 1\}^n$. Then
$$
\left|\mathbb{E}[f(Y)] - \mathbb{E}[f(U)]\right| \leq \epsilon.
$$
Proof: We can use the Fourier expansion of the AND function:
$$
f(x) = \sum_{T \subseteq [m]} \frac{(-1)^{|T|}}{2^m} \cdot \prod_{i \in T} (-1)^{\oplus_{j \in P_i} x_j} = \sum_{T \subseteq [m]} \frac{(-1)^{|T|}}{2^m} \cdot (-1)^{\bigoplus_{i \in T, j \in P_i} x_j}
$$
For a fixed $T \subseteq [m]$, we have
$$
|\mathbb{E}[(-1)^{\oplus_{i \in T, j \in P_i} Y_j}] - \mathbb{E}[(-1)^{\oplus_{i \in T, j \in P_i} U_j}]| \leq 2 \cdot |\mathbb{E}[\oplus_{i \in T, j \in P_i} Y_j] - \mathbb{E}[\oplus_{i \in T, j \in P_i} U_j]| \leq \epsilon.
$$
Therefore, by the triangle inequality,
$$
|\mathbb{E}[f(Y)] - \mathbb{E}[f(U)]| \leq \sum_{T \subseteq [m]} \frac{\epsilon}{2^m} = \epsilon. \qquad \square
$$
Your condition, that $|S \cap P|$ and $|S \cap Q|$ are both odd, can be rephrased as a function $f$ as in the claim by considering the indicator vectors of all the sets under consideration. Under the uniform distribution, the condition is satisfied with probability $1/4$. Therefore, it suffices to take $X$ to be the support of an $\epsilon$-biased distribution with $\epsilon < 1/4$. Plugging in known constructions of small-biased distributions gives an explicit construction with $|X| = O(n)$.


What type of automaton is Google's Turing Doodle? In celebration of Alan Turing's birthday, Google published a doodle showing a machine. What kind of machine is the doodle? Can it express a Turing Complete
language?

There are obvious differences to the classical turing machine: a finite tape, constraints in how state can be connected,...

The doodle is still be available here

(The display on the top right shows the expected output.)

The  tape in the middle is divided into squares that can hold a blank, a zero or a one. The head is positioned above one of the squares and is used for reading and writing.

Below the tape you can see a green arrow which you can click on to start the machine. There are two lines of circles next to it, some of which are connected. I will call them "states".

After the machine starts, the first state to the right of the green button lights up, then the next one to the right, and so on... Each state contains one of the following commands:

blank = do nothing (just move to the next state)
1 = write a one to the tape at the current position of the head
0 = write a zero to the tape at the current position of the head
arrow to the left = move the head one step to the left
arrow to the right = move the head one step to the right
condition: if the value under the head is equal to the value shown in the square go down to the second line of states. if not, move to the next state to the right
left jump: return to a (fixed) previous state but only on the upper row [I originally forgot that one, thanks  @Marzio!]

There is no way to "overlap" two jumps (one over another).
The machine stops when there it leaves a state and there is no next state to the right of it.

(After the machine stops the contents of the tape are compared to the contents of the display, but I don't consider that to be part of the intended functionality of the machine.)

Assuming that:

we can add an arbitrarily large number of rows ("status lines")
the rows can be arbitrarily long
the tape is infinite

I tried to build an Alan Turing's Doodle machine configuration that emulates the machine $M_4$ described in "Small Turing Machines and generalized busy beaver competition" that has a halting problem that depends on an open (up to my knowledge) Collatz-like problem. The full picture is available here.

... so even if the A.T.'s Doodle is perhaps not Turing complete (due to the non-overlapping left-only jump operator available only in the first row), it is powerful enough to walk the fine line of (un)decidability :-D

EDIT: TURING DOODLE IS TURING COMPLETE

(I leave the previous answer above, because I'm not sure that this part is correct :-)

I think that even with a single left non-overlapping jump the Turing Doodle is Turing complete!. The (simple) idea is to use the tape itself to store the current state and use multiple cells to represent a larger alphabet.

For example a 2 states 8 symbols TM can be simulated using the following tape representation:

    HEAD POSITION
    v
...[s][b2 b1 b0] [_][b2 b1 b0] [_][b2 b1 b0] ....
   ^^^^^^^^^^^^^
    "macro cell"

The Turing doodle can:

read $s$ and branch to one of the two different horizontal areas representing STATE A and STATE B;
read $b2, b1, b0$ and branch to a row representing one of the eight symbols;
write the next symbol, move the head to the "macro cell" on the left or right, and store on it the next state; in the figure below these operations (that can be done on a sequence of cells using the actions move left/right and write) are called "MW";
finally transfer the control to the upper row that with a single left jump will bring the control back to step 1.

The full picture is available here.

In the same manner, given a $TM$ with an arbitrary number of states and alphabet symbols we can build an equivalent Turing Doodle machine $DM$.


K-fold Traveling salesman problem - A variant of TSP Consider a weighted graph $K_n$ and where the weights between vertices $i,j$ is $w_{ij}$. Consider a path, $\sigma$, passing through each vertex only once. Here $\sigma_i$ is the vertex in the $(i\%n)^{th}$ step of the path. (For example, $\sigma_{n+1} = \sigma_1$)

Traveling salesman problem (TSP) minimizes the following objective : $$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}$$

A variant of TSP, 2-Fold TSP, will additionally consider the weights between the 1-skipped vertices on the path. The objective of a 2-Fold TSP is to minimize

$$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}+w_{\sigma_i,\sigma_{i+2}}$$

and similarly the objective of K-fold TSP is to minimize

$$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}+w_{\sigma_i,\sigma_{i+2}}+\cdots+w_{\sigma_i,\sigma_{i+k}}$$

Question

Can this be reduced to the original TSP?
Is there any reference which deals with k-fold TSP? What is the name of this problem in the literature?
Any heuristics/approximation algorithms?

There was a paper on the arxive last month, dealing with this generalization of the TSP:

  The multi-stripe travelling salesman problem
  Eranda Cela, Vladimir Deineko, Gerhard J. Woeginger
  (Submitted on 20 Sep 2016)
  https://arxiv.org/abs/1609.09796

The problem does not seem to have a particular name in the literature.


Enumerating all simply typed lambda terms of a given type How can I enumerate all simply typed lambda terms which have a specified type?

More precisely, suppose we have the simply typed lambda calculus augmented with numerals and iteration, as described in this answer. How can I enumerate all lambda terms of type N (natural number)?

For example, the first few lambda terms of type N are

zero
succ zero
succ (succ zero), K zero zero
succ (succ (succ zero)), K zero (suc zero), K (suc zero) zero, iter zero suc zero

and so on. How can I systematically continue this pattern, while ensuring that only well-typed terms are generated?

This question has been considered several times in the academic community, from the practical:

Yakushev & Jeuring, Enumerating Well-Typed Terms Generically

Fetsher & al, Making Random Judgments: Automatically Generating
Well-Typed Terms from the Definition of a Type-System

to the more theoretical

Grygiel & Lescanne, Counting and generating lambda terms

Implementations can pretty easily be found online. I didn't find any that addressed a system with iterators per se, but it shouldn't be a stretch from what already exists.


TSP with "enemy" nodes I am curious if the following variation of the traveling salesman problem (TSP) (or a vehicle routing problem (VRP) version) occurs in the literature and has a name I could search for.
The story/idea is we have ally locations and enemy locations. We want to visit all allies while encountering few enemies. I thought of this when reading some papers in combinatorial optimization, but this is not my area of expertise. So, I don't know if I am searching the correct words.
The graph theoretic formulation is that we have an edge weighted graph $G = (V,E)$ which is bicolored so $V = A \cup B$ (note the coloring need not be proper, i.e. $G$ doesn't have to be bipartite). We are given an integer $k$ and want to find a minimum weight cycle (or alternatively path) which contains all vertices in $A$ and at most $k$ vertices in $B$.
Has this problem been studied somewhere? Does it have a name or fit inside a known generalized TSP? Or maybe there is some reduction to known version of TSP?
When $k=0$ we can delete vertices in $B$ along with all edges incident to them and we have the usual TSP.

As TSP is an optimization problem, there are not many variants of it (that I know of) that add hard constraints to the formulation. But if I have understood correctly, your problem is a special case of (a variant of) the Prize-Collecting Travelling Salesman Problem (PCTSP), which seems to be introduced in [1] (NB: Technical report, written on typewriter. Hard to read):
Given a graph $G$ and a prize $w_v$ and a penalty $p_v$ for each vertex $v \in G$, you are asked to construct a tour that minimizes the cost of travelling, plus the penalty for every vertex you do not visit. In addition, you have the constraint that the combined prize for every vertex you do visit must be higher than some prescribed sum $W$.
If you are allowed to put negative values on your prizes, your problem can be formulated as a PCTSP this way:

Let $p_v = 0$ for every $v\in V$
Let $w_a = n$ for every $a\in A$
Let $w_b = -1$ for every $b\in B$
Let $W = n\cdot |A| - k$

It's worth it to add that having shorter routes often will lead to cheaper tours anyway. For example, if $G$ is metric, then you can just solve TSP on $G[A]$, as visiting any vertices in $B$ will be considered a detour.
[1] Balas, Egon, The prize collecting traveling salesman problem, Networks 19, No. 6, 621-636 (1989). ZBL0676.90089.


Not-one 3-SAT; How hard is it? I have the following problem:

We are given an instance of the 3-SAT problem.
Is there a satisfying assignment s.t. at least two literals are satisfied in each clause?

The question is:

Is the problem NP-complete?

The question might sound stupid, but I couldn't figure it out by myself.

I searched the web and in books but didn't find anything.

I also tried to reduce 3-SAT to it, but without success.

(I have to admit that I didn't spent much time to do it since it is not my main research focus; this is just a question that came to my mind while working on another problem. I am interested in the answer because if it turns out to be NP-complete it could help me in a future problem.)

Thanks in advance for your answers! Every answer or comment is welcome.

At least two of the literals $x$, $y$, $z$ are satisfied iff at least one literal in each pair $(x,y)$, $(x,z)$, $(y,z)$ is satisfied. Therefore it is a special case of 2SAT, and there is a polynomial-time algorithm for solving it.


Is this an equivalent condition for algebraic posets? The definition of "algebraic poset" in Continuous Lattices and Domains, Definition I-4.2, says that, for all $x \in L$,

the set $A(x) = {\downarrow} x \cap K(L)$ should be a directed set, and
$x = \bigsqcup ({\downarrow} x \cap K(L)$.

Here $L$ is a poset, $K(L)$ is the set of compact elements of $L$, and ${\downarrow} x$ means $\{y \mid y \sqsubseteq x\}$.

I was a bit surprised by the first condition.  It is an easy argument to show that, if $k_1$ and $k_2$ are in $A(x)$ then $k_1 \sqcup k_2$ is also in $A(x)$.  So, all nonempty finite subsets of $A(x)$ have upper bounds in it.  The only question is whether the empty subset has an upper bound in it, i.e., whether $A(x)$ is nonempty in the first place.  So,

Is it ok to replace the first condition with $A(x)$ is nonempty?
What is an example of a situation where $A(x)$ is empty?

Note added: How is $k_1 \sqcup k_2$ in A(x)?  First, since $k_1 \sqsubseteq x$ and $k_2 \sqsubseteq x$, we have $k_1 \sqcup k_2 \sqsubseteq x$.  Second, $k_1$ and $k_2$ are compact.  So, any directed set that goes "beyond" them must "pass" them.  Suppose a directed set $u$ also goes beyond $k_1 \sqcup k_2$, i.e., $k_1 \sqcup k_2 \sqsubseteq \bigsqcup u$.  Since it has gone beyond $k_1$ and $k_2$, it must have passed them, i.e., there are elements $y_1, y_2 \in u$ such that $k_1 \sqsubseteq y_1$ and $k_2 \sqsubseteq y_2$.  Since $u$ is a directed set, it must have an upper bound for $y_1$ and $y_2$, say $y$.  Now, $k_1 \sqcup k_2 \sqsubseteq y \in d$.  This shows that $k_1 \sqcup k_2$ is compact.  The two pieces together say $k_1 \sqcup k_2 \in A(x)$.

An example where $A(x)$ is empty is the set of real numbers $\mathbb{R}$ with the usual ordering. It has no compact elements at all.

If we assume the second condition then $A(x)$ cannot be empty: if $A(x) = \emptyset$ then by the second condition $x$ is the empty join, therefore the least element of $L$, which is compact, therefore $x \in A(x) = \emptyset$, a contradiction.

Your proposal to replace the first condition with non-emptyness does not work. Consider the poset $L$ which consists of two copies of $\mathbb{N}$ and $\infty$, where we write $\iota_1(n)$ and $\iota_2(n)$ for the two copies of $n$, ordered by:

$\iota_1(m) \leq \iota_1(n) \iff m \leq n$
$\iota_2(m) \leq \iota_2(n) \iff m \leq n$
$x \leq \infty$ for all $x$.

In words, we have two incomparable chains with a common supremum. All elements are compact except $\infty$. Now:

${\downarrow}x \cap K(L) \neq \emptyset$, obviously.
$x = \bigvee ({\downarrow}x \cap K(L))$, obviously.
The set ${\downarrow}\infty \cap K(L) = \mathbb{N} + \mathbb{N}$ is not directed.


Is there a generalization of information theory to polynomially knowable information? I apologize, this is a bit of a "soft" question.

Information theory has no concept of computational complexity. For example, an instance of SAT, or an instance of SAT plus a bit indicating satisfiability carry the same amount of information.

Is there a way to formalize the concept of "polynomially knowable"?

Such a framework could define for example the notion of polynomial-KL divergence between a random variable X relative Y as the number of bits needed to compute X in polynomial time given Y.

Likewise, the entropy of a random variable X could be defined as the number of bits needed to encode X in a way that can be decoded in polynomial time.

Has such a generalization been studied? Can it be made consistent?

Yes. Time-bounded Kolmogorov complexity is at least one such "generalization" (though strictly speaking it's not a generalization, but a related concept). Fix a universal Turing machine $U$. The $t(n)$-time-bounded Kolmogorov complexity of a string $x$ given a string $y$ (relative to $U$), denoted $K^t_U(x | y)$ (the subscript $U$ is often supressed) is defined as the shortest string $p$ (a "program" for $U$) such that $U(p,y)=x$ and such that the computation of $U(p,y)$ takes at most $t(|x|)$ time. If you take this as your definition of "conditional information", then you can likewise define all the usual concepts from information theory.

However, in this time-bounded setting, not all of the usual theorems of information theory are known to hold. For example, symmetry of information is known to hold for usual Kolmogorov complexity (no time bound), but not known to hold for time-bounded. See, for example, Chapter 6 of Troy Lee's thesis.

If you are concerned that this applies to strings rather than distributions, I suggest reading the following papers, which say that in fact Kolmogorov complexity of strings and Shannon entropy of distributions are very closely related:

Grunwald and Vitanyi. Shannon Information and Kolmogorov Complexity
Hammer, Romashchenko, Shen, Vereshchagin. Inequalities for Shannon Entropy and Kolmogorov Complexity.

(On the other hand, there are some properties that are known not to be shared between the two, see Muchnik & Vereshchagin, Shannon Entropy vs. Kolmogorov Complexity.)


On succinct $EXP$ and $NEXP$ complete problems? We know succinct version of many $P$-complete problems are $EXP$-complete. There are standard ways to define $EXP$-complete graph problems from succinct representations of these $P$ complete problems.

What is the standard way to define $EXP$-complete problem from succinct representations of $P$ complete problems that do not come from graphs if there are any?

For example what is the succinct version of the $P$-complete iterated mod problem $$\mbox{given }a, b_1, b_2,\dots, b_n\in\Bbb Z,\mbox{ is }((\dots((a \bmod b_1) \bmod b_2) \dots) \bmod b_n) = 0$$ and would that be $EXP$-complete and what is the succinct version of linear programming and would that be $EXP$-complete?

Is there a higher version of $ETH$ (Exponential Time Hypothesis) that is applicable to the $EXP$ versus $NEXP$ problem for $NEXP$ complete problems that come from succinct version of $NP$ complete problems?

The description of a succinct problem has very little to do with graphs, per se. Given a language $L \subseteq \Sigma^*$, we can define its succinct version as the set of Boolean circuits $C$ such that, if $C$ has $m$ inputs, then the string $s$ of length $2^m$ which is the concatenation of $C(0^m) C(0^{m-1} 1) C(0^{m-2} 10) \dotsb C(1^m)$ is in $L$.
You can make such a version, though I haven't seen it studied before. The smallest known upper bound on the deterministic time complexity of $\mathsf{NEXP}$ is $\mathsf{EEXP} = \mathsf{DTIME}(2^{2^{n^{O(1)}}})$, so you could conjecture that a standard $\mathsf{NEXP}$-complete problem is not in significantly sub-doubly-exponential time.


When does randomization stops helping within PSPACE It is known that adding bounded-error randomization to PSPACE doesn't add power. That is, BPPSAPCE=PSPACE.

It is famously unknown whether P=BPP, but it is known that $BPP\subseteq \Sigma_2\cap \Pi_2$.

Thus, it is possible (while conjectured to be false) that adding probability to P adds expressive power.

My question is whether we know (or have evidence of) the border between P and PSPACE where adding randomization no longer adds power.

Specifically,

  Are there any problems that are known to be in $BP\Sigma_i$ (resp. $BP\Pi_i$) that are not known to be in $\Sigma_i$ (resp. $\Pi_i$)? And similarly for $BPPH$ v.s. $PH$?

There is a difficulty with the premise of your question — "when does randomization stops helping within $\mathrm{PSPACE}$ — because it suggests that the computational classes $\mathrm{X}$ such that $\mathrm{P \subseteq X \subseteq PSPACE}$ form some sort of linear hierarchy when this is not evident.

We can illustrate this by comparisons between the polynomial hierarchy and counting classes. As Emil Jeřábek indicates in the comments,
   $$\begin{align*} \mathrm{BP\cdot \Sigma_i^p \subseteq \Pi_{i+1}^p} &&\text{and}&&  \mathrm{BP\cdot \Pi_i^p \subseteq \Sigma_{i+1}^p} \end{align*}$$
 by relativisation of $\mathrm{AM \subseteq \Pi_2^p}\,$; and therefore $\mathrm{BP \cdot PH = PH}$. On the other hand, Toda's Theorem shows that
$$\mathrm{PH \subseteq BP\cdot\oplus P}.$$
If you suppose that "randomization has stopped adding power by the time you ascend to $\mathrm{PH}$", then you will be tempted to suspect that because $\mathrm{PH \subseteq BP \cdot \oplus P}$, perhaps in fact $\mathrm{BP \cdot \oplus P = \oplus P}$. But I don't know that anyone conjectures this, or even that $\mathrm{PH \subseteq \oplus P}$ (which would be a necessary consequence); I think that any result of this sort would be considered a major breakthrough.

Of course, if you only care about the polynomial hierarchy, and more generally (to scale up to $\mathrm{PSPACE}$) quantified boolean formulas, then you can extract some sort of linear answer to your question — in which case Emil's comments are about as complete an answer as you are likely to get.


Is it $NP$-complete to decompose bridgeless cubic bipartite graph into edge-disjoint paths of length 3? Motivated by this post on cubic graphs decompositions, I am interested in decomposing a connected bridgeless graph into edge-disjoint paths of length 3 (P4). My intuition is that it should be NP-complete but did not find a reduction.

I am aware that it is $NP$-complete to decide whether a cubic bipartite planar graph is decomposable into vertex-disjoint paths of length 2 (P3).

  Is it $NP$-complete to decide whether a bridgeless cubic bipartite graph is decomposable into edge-disjoint paths of length 3 (P4)?

In a related note, Barnette conjecture states that every 3-connected cubic bipartite planar graph is Hamiltonian. This is equivalent to decomposing every such graph into Hamiltonian cycle and a perfect matching. Feder and Subi proved that if there is a single graph in the class of the conjecture which does not admit such decomposition then deciding the existence of Hamiltonian cycle in $NP$-complete in that class.

  For general connected cubic graph decomposition problems, under which conditions does the existence of a non-decomposable graph imply the $NP$-completeness of the decomposition problem?

EDIT For the second question, Is there a subclass of connected bridgeless cubic graphs where non-decomposable graphs exist but it is polynonial time to decide the existence of a (edge) decomposition?

The linked post on MthOverflow provides some interesting examples of connected cubic graph decomposition problems.

EDIT The problem is posted on MathOverflow: Connection between Barnette conjecture and hardness of cubic graph decomposition

As pointed out by David Eppstein when I asked a related question a while ago: you can do that in polynomial time.

The idea is to find a perfect matching $M$ (which exists and can be found in polynomial time since your graph is cubic and bridgeless), and then to use the edges of $M$ as middle edges of the $P_4$'s.

To complete the construction, remove the edges of $M$ and orient the remaining cycles arbitrarily. Then attach to each edge $\{u, v\}$ of $M$ the arcs going out from $u$ and $v$, and you are done.


Lower bound on prefix code lengths For a prefix code $C:\{0,1\}^*\to\{0,1\}^*$, define $f(n)$ as the length of the longest encoding of a number with up to $n$ bits:
$$
f(n)=\max_{|k|\le n}\left|C(k)\right|.
$$

(Note that by taking input as $\{0,1\}^*$ rather than $\mathbb{Z}^+$ I'm distinguishing between the 1-bit number 1 and the 2-bit number 01.)

The counting bound gives $f(n) \ge \left\lceil\log\left(2^n+2^{n-1}+\cdots+2^0\right)\right\rceil = \left\lceil\log\left(2^{n+1}-1\right)\right\rceil = n+1$ for $n>0$ where, throughout this post, $\log$ denotes the binary logarithm.

It's easy to construct $C$ such that $f(n)=O(n)$, $f(n)=n+O(\log n)$, $f(n)=n+\log n+O(\log\log n),$ etc. by recursion (starting from, say, Elias gamma coding). Is there a prefix-free code with $f(n)\le n+(1-\varepsilon)\log n$ for some $\varepsilon>0$ and large $n$?

I'll try to show this, hope I interpreted the question correctly.

Let $A_k=\{0,1\}^k.$ If $f(n)\leq n+\log n$ for $n$ large enough this implies $$\max\{\ell(c(x)):x \in A_1 \cup A_2\cup \ldots \cup A_k \}\leq k+ \log k,$$ for $k\geq N$, for some finite $N$, where $\ell(c(x))$ is the length of the codeword $c(x)$ assigned to $x.$ So this means that
$$
\sum_{N\leq k ~~} \sum_{x \in A_1\cup A_2 \cup \ldots \cup A_k} 2^{-\ell(c(x))}\geq \sum_{N \leq k~~} \sum_{x \in A_1\cup A_2 \cup \ldots \cup A_k} 2^{-(k+\log k)}
$$
which is equal to
$$
\sum_{N\leq k} |A_1 \cup A_2 \cup \ldots \cup A_k|~ 2^{-(k+\log k)}=
\sum_{N\leq k} (2^{k+1}-1)~ 2^{-(k+\log k)}
$$
which is equal to
$$
\sum_{N\leq k} 2^{1-\log k} - 2^{-(k+\log k)}=2 \sum_{N\leq k} \frac{1}{k} - \sum_{N\leq k}\frac{2^{-k}}{k}=2 \left(\sum_{N\leq k} \frac{1}{k}\right) -\ln 2
$$
which is unbounded, since the harmonic series diverges.


Placing color boxes on a colored image such that color consistency is maximized I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem.

Given an image with black background that contains blobs whose colors are taken from a set C (that does not contain black). Suppose that we have an infinite number of rectangular bounding boxes such that:

Each bounding box has a color taken from C.
Every bounding box of color c has width w_c and height h_c.

Question: How to place these bounding boxes on the image such that there is no overlap between any two boxes, and that n_good - n_bad is maximized, where n_good is the total number of pixels that are inside a box of the same color (as the pixel's color), and n_bad is the total number of pixels that are inside a box of a different color?

Any suggestions on how to solve this problem would be very much appreciated!

Thank you very much in advance for your help!

Just an extended note to show that the decision version of your problem ("Is there a placement of the bounding boxes such that $n_{good} - n_{bad} \geq k$?" ) is NP-complete even for two colors $C = \{c_1, c_2\}$ and two bounding boxes $B_1 \equiv \langle col=c_1, w=3, h=1 \rangle$, $B_2 \equiv \langle col=c_2, w=1, h=1 \rangle$.

The reduction is straightforward from: Danièle Beauquier, Maurice Nivat, Eric Rémila, Mike Robson: Tiling Figures of the Plane with Two Bars. Comput. Geom. 5: 1-25 (1995)

They prove that tiling a figure on the plane grid with two horizontal/vertical bars with length at least 3 is NP-complete.

The reduction to your problem is simple: just color the "pixels" of the figure with color $c_1$ and fill the remaining background pixels of the $N+1\times N+1$ square region around it with color $c_2$. You can place the bounding boxes $B_1, B_2$ with $n_{good} - n_{bad} = (N+1)^2$ if and only if the original figure is tileable with $3 \times 1$ horizontal/vertical bars.


Is there a list of forbidden subgraphs for comparability graphs? The "graph classes: a survey" mentioned Trotter and other authors have presented a list of forbidden subgraph of comparability graph. But the google book( where I read graph classes: a survey) do not have the page which contains the reference of specific literature.
To my knowledge, one forbidden graph is "a k-cycle ( k is an odd intege $\ge$ 5) and no triangle chord".

Thank you for your help in advance. :-)

You could refer to the entry for comparability graphs on graphclasses.org: http://www.graphclasses.org/classes/gc_72.html
(look at "equivalent classes" and note that the list is not finite)


DNA-algorithms and NP-completeness What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they be used to solve instances of NP-complete problems like TSP that von Neumann machines can not solve feasibly in practice?

Soundbite answer: DNA computing does not provide a magic wand to solve NP-complete problems, even though some respected researchers in the 1990s thought for a time it might.

The inaugural DNA computing experiment was performed in a laboratory headed by the renowned number theorist Len Adleman.  Adleman solved a small Traveling Salesman Problem -- a well-known NP-complete problem, and he and others thought for a while the method might scale up.  Adleman describes his approach in this short video, which I find fascinating.  The problem they encountered was that to solve a TSP problem of modest size, they would need more DNA than the size of the Earth.  They had figured out a way to save time by increasing the amount of work done in parallel, but this did not mean the TSP problem required less than exponential resources to solve. They had only shifted the exponential cost from amount-of-time to amount-of-physical material.

(There's an added question: if you require an exponential amount of machinery to solve a problem, do you automatically require an exponential amount of time, or at least preprocessing, to build the machinery in the first place?  I'll leave that issue to one side, though.)

This general problem -- reducing the time a computation requires at the expense of some other resource -- has shown up many times in biologically-inspired models of computing.  The Wikipedia page on membrane computing (an abstraction of a biological cell) says that a certain type of membrane system is able to solve NP-complete problems in polynomial time.  This works because that system allows for the creation of exponentially-many subobjects inside an overall membrane, in polynomial time.  Well... how does an exponential amount of raw material arrive from the outside world an enter through a membrane with constant surface area?  Answer: it's not considered.  They're not paying for a resource that the computation would otherwise require.

Finally, to respond to Anthony Labarre, who linked to a paper showing AHNEPs can solve NP-complete problems in polynomial time.  There's even a paper out showing AHNEPs can solve 3SAT in linear time.  AHNEP = Accepting Hybrid Network of Evolutionary Processors.  An evolutionary processor is a model inspired by DNA, whose core has a string that at each step can be changed by substitution, deletion, or (importantly) insertion.  Further, an arbitrarily large number of strings is available at every node, and at each communication step, all nodes send all their correct strings to all attached nodes.  So without time cost, it's possible to transfer exponential amounts of information, and because of the insertion rule, individual strings can become ever larger over the course of the computation, so it's a double whammy.

If you are interested in recent work in biocomputation, by researchers who focus on computations that are real-world practical, I can offer this book review I recently wrote for SIGACT News, which touches briefly on multiple areas.


PCP theorem and proof complexity? It is known that if $P=NP$ then $CoNP= PCP[O(log(n)),O(1)]$. Also, it is known that $NEXP=PCP[poly(n),poly(n)]$. It appears that PCP can't tell us which natural problems are not in $NP$. I wonder if it is possible to use PCP characterization to separate $CoNP$ from $NP$.

  What are the best bounds on randomness complexity $r(n)$ and query complexity $q(n)$ such that Tautology Problem is in $PCP[O(r(n)),O(q(n))]$?

I think the following paper will help:
Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy

It states that $\mathbf{coNP} \not\subset \mathbf{IP}[\log^{O(1)} n]$ unless the exponential hierarchy collapses. ($\mathbf{IP}[k]$ is the class of languages possessing $k$-move interactive proofs.)

Regarding the natural relation between interactive & probabilistically checkable proofs, I think the above result must help.

I also suggest taking a look at A New Sampling Protocol and Applications to Basing Cryptogaphic Primitives on the Hardness of NP.


Sparsity of Horn satisfiability? Is the set of satisfiable Horn formulas sparse?

A sparse language contains a polynomially bounded number of srings at every length.

No. Fix a $k$, and let $x_1, x_2, ..., x_k$ be the variables in your Horn formula. Then for all $i$ the clause $(x_i)$ is a Horn clause – there is at most one positive literal. Using such clauses, you can construct $2^k - 1$ different Horn formulas: $(x_1)$; $(x_2)$; $(x_1) \wedge (x_2)$; $(x_3)$; etc. Each of these is trivially satisfiable – just set $x_i = 1$ for all $i$. The length of each formula is $O(k \log k)$, assuming any reasonable encoding.

(You can add extra requirements like "all clauses must contain at least one negative literal", "all variables must occur in at least one clause", etc., but this doesn't really change anything; just tweak the above construction slightly.)


Ambiguity in regular and context-free languages I understand the following claims to be true:

Two distinct derivations of a string in a given CFG may sometimes attribute the same parse tree to the string.
When there are derivations of some string in a given CFG that attribute different parse trees, the CFG is ambiguous.
Some context-free languages generated by ambiguous CFGs are also generated by unambiguous CFGs.
Some languages are such that the only CFGs that can generate them (and there are some such) are ambiguous.

Q1. I understand it also to be undecidable whether an arbitrary CFG is ambiguous, in the sense of point 3 above. Or is it rather that it's undecidable whether a context-free language is ambiguous, in the sense of point 4? Or are both undecidable?

Q2. Which of points 1-4 become false when we replace "context-free" with "regular"? Are regular grammars and languages always unambiguous?

About Q1:
Both the ambiguity problem (given a CFG, whether it is ambiguous) and the inherent ambiguity problem (given a CFG, whether its language is inherently ambiguous, i.e. whether any equivalent CFG is ambiguous) are undecidable.  Here are the original references:

The undecidability of ambiguity was proved by Cantor (1962), Floyd (1962), and Chomsky and Schützenberger (1963).  The proofs in textbooks typically reduce from the Post Correspondence Problem.
The undecidability of inherent ambiguity was proved by Ginsburg and Ullian (1966).

About Q2:  A regular grammar is a "one-sided linear" context-free grammar, where at most one nonterminal appears in any rule right-part, and where that nonterminal is at the last (in right linear grammars) or first (in left linear grammars) position.  Such grammars are easily translated into equivalent finite-state automata (roughly by considering each nonterminal as a state), which are unambiguous iff the regular grammar is unambiguous.  The class of unambiguous regular grammars and unambiguous automata has been studied in particular by Stearns and Hunt (1985), who show that they enjoy tractable algorithms for the inclusion problem.

About the relationship between derivations (i.e. sequences of rules applications $\beta A\gamma\Rightarrow \beta\alpha\gamma$ where $A\to\alpha$ is a rule of the grammar) and derivation trees (i.e. where a node labeled $A$ is the parent of a sequence of nodes $X_1,\dots,X_m$, where $A\to X_1\cdots X_m$ is a rule): in a general CFG, there can be different derivations, which visit the same derivation tree in different ways.

These different derivations occur because one has a choice between applying a grammar rule in two different places in a sentential form: in a sentential form $\gamma A\eta B\theta$ with at least two nonterminals $A$ and $B$, one can apply $A\to\alpha$ first and obtain $\gamma\alpha\eta B\theta$, or $B\to\beta$ first and obtain $\gamma A\eta\beta\theta$, but applying the other rule will lead to the same $\gamma\alpha\eta\beta\theta$.  Imposing leftmost (always deriving the leftmost nonterminal in any sentential form) or rightmost derivations imposes a fixed order for visiting derivation trees, and there is then a single derivation for a given derivation tree.

In a linear context-free grammar, there is no such choice, since there is at most one nonterminal in any sentential form, and there is a single derivation for a given derivation tree, which is both leftmost and rightmost.
Having two different parse trees with the same yield $w$ (sequence of leaves) is the definition of $w$ being ambiguous, it does not change when considering regular grammars.  Alternatively, one can also ask for two different leftmost derivations.  Note that a derivation in a one-sided grammar corresponds to an accepting run in its associated finite-state automaton, which is called ambiguous exactly in the same way: when there exist two different accepting runs for a given input $w$.
and 4.$~$  If you take the finite-state automata view, it suffices to determinize your ambiguous automaton in order to obtain an unambiguous automaton for the same language: there will be a single run for any given word.  This deterministic automaton is equivalent to an unambiguous regular grammar.

To answer your comment: there exist ambiguous regular grammars, for instance $S\to A\mid B,\,A\to a,\,B\to a$ has two leftmost derivations for $a$: $S\Rightarrow A\Rightarrow a$ and $S\Rightarrow B\Rightarrow a$.  An equivalent unambiguous grammar is $S\to a$.

About the relation with Q1: it is decidable whether a regular grammar is ambiguous (the inherent ambiguity problem is not very challenging on regular grammars, since the answer is invariably "no" without even looking at the input grammar).  This can be checked in $O(|G|^2)$ using a squaring construction on its associated automaton: construct the product of the automaton with itself, and see whether some state $(q,q')$ with $q\neq q'$ is accessible and co-accessible.  The oldest reference I know for this idea is a paper by Even (1965).


How to come up with an non-trivial idea in theoretical computer science? I am a PhD student working in theoretical computer science. I have read the research papers of many researcher and I have seen many tools and mathematics they use for designing an algorithm. For example see this research paper [Primality in P]. I would not say this research paper is based on one or two ideas but it is based upon many ideas which requires serious mathematics. I am struggling to come up with those kind of ideas from couple of years. I have worked on one problem for many months, but there is nothing non-trivial coming into my mind. All the ideas which have come into my mind till now are trivial and of very little use to theoretical computer science researchers. I am wondering how to come up with a machinery which will enable me to generate non-trivial results.

Question : How to come up with a non-trivial idea in theoretical computer science? I know there are different meanings to the word "non-trivial idea". For me, it is something publishable and interesting to the theoretical computer science community. I have seen some research papers in which they define few (mathematical) terms then design the algorithm using the defined terms. I wondering how to come up with such things.

One advice I have got from my research friends and seniors is to read the research papers carefully and read the mathematics (theorems and proofs) very carefully, try to do the proofs on your own and try to extend them.

Almost certainly there are lists of open problems in your particular subfield.  Find them and read them.  Although it's rather unlikely you will be able to solve these problems --- at least right away ---, use them as a starting point.  Can you solve some particular cases?  Can you solve a less general problem?  Can you show a more general problem is computationally difficult?
Read what other people are doing.  This means making a list of the conferences and journals in your area, and devoting at least an hour a day to reading papers in them.  There is no need to understand everything at once.  Try to familiarize yourself with the general themes, then pick one or two papers that seem interesting or fundamental and immerse yourself in them.  Study the
techniques and proofs.  Can you apply them to similar or related problems?  Work out specific examples in detail, to the extent possible.
When reading any result, ask yourself:  are all the hypotheses necessary?  What if the hypotheses are weakened or strengthened?  Are the bounds really optimal?  If only an upper bound is proved, can you prove a matching lower bound?


Multidimensional B+ tree I've got an idea for indexing multidimensional data. I haven't been able to find anything equivalent and am wondering if it is indeed a novel approach.

The idea is a 'stacked' B+ tree implementation where the leaf nodes contain both the dimension data and a pointer to the next dimension. Each dimension is in itself a B+ tree. It is similar to how Range Trees link/point to the next dimension. However, it is different from a Range Tree by using a B+ tree instead of a straight binary search tree.

Also, the elements in each B+ tree layer are unique and are stored with the number of records belonging to each leaf value.

I believe the search complexity would be $(\sum_{i=0}^{d-1} \log _{B} \text{card}(n^{i})) + k$.

Where $\log _{B}$ comes from the branching factor of the B+ tree, $\text{card}(n^{i})$ is the number of unique elements stored for each dimension and $d$ is the number of dimensions stored. $k$ is simply the number of elements returned.

Has anyone written / designed a similar search algorithm before?

No, this is not new; range searching with multilevel B-trees is completely standard.  See, for example, the following surveys:

Lars Arge.
External memory data structures.  Handbook of Massive Data Sets (James Abello, Panos M. Pardalos, and Mauricio G. C. Resende, eds.), 313-357.  Kluwer Academic Publishers, 2002.  See especially sections 5 and 6.
Jeffrey Scott Vitter.  Algorithms and data structures for external memory.
Foundations and Trends in Theoretical Computer Science 2(4): 305–474, 2008.
See especially section 12.


Is it possible to find if a sequence exists in polynomial time in the following problem? I've been thinking about the following problem for a time, and I haven't found a polynomial solution for it. Only brute-fource. I've been trying to reduce an NP-Complete problem into it too with no sucess.

Here is the problem:

You have a sorted set $\{(A_1, B_1), (A_2, B_2), \ldots, (A_n, B_n)\}$ of positive integers pairs.

$(A_i, B_i) < (A_j, B_j) \Leftrightarrow A_i < A_j \lor (A_i = A_j \land B_i < B_j)$
$(A_i, B_i) = (A_j, B_j) \Leftrightarrow A_i = A_j \land B_i = B_j$

The following operation can be applied to a pair: Swap(pair). It swaps the elements of the pair, so $(10, 50)$ will become $(50, 10)$

When a pair in the set is swapped, the set automatically gets sorted again (the swapped pair is out of place and it will get moved into its place in the set).

The problem consist on see if there is a sequence that, starting on some pair, swaps the entire set, with the following condition:

After a pair is swapped, the next pair to be swapped has to be either the successor or the predecesor pair in the set.

It would be great to find a polynomial time solution to this problem, or a reduction of an NP-Complete problem into it.

Note:
It's already a decision problem. I don't want to know which the sequence is: only if a sequence exists.

Example of how the set gets sorted after swapping a pair

$\textbf{(6, 5)}$
$(1,2)$
$(3,4)$
$(7,8)$

If I swap the first pair, it becomes to: $(5,6)$, and after sorting the set (placing the sorted pair in its new position), we have:

$(1,2)$
$(3,4)$
$\textbf{(5,6)}$
$(7,8)$

Then I have to swap either the $(3,4)$ (predecessor) pair or $(7,8)$ (sucessor), and repeat the process until all pairs are swapped (if possible).

Important:
You cannot swap an already swapped pair.
If there is a sequence of 'swap' operations, then all pairs has to be renamed to once and only once.

Example where isn't possible to swap all pairs

$(0, 0)$
$(1, 4)$
$(3, 2)$
$(5, 5)$

... I searched some patterns to build a reduction from a NPC problem, but didn't find a way to represent a "flow" with a "fork" ...

So (after some work) this is a polynomial algorithm ...

ALGORITHM

The starting list can be viewed as an array of $N*2$ consecutive "holes". For each initial pair $(a_j,b_j)$, put the "element" $b_j$ at hole number $a_j$. Each pair can be viewed as a directed edge from position $a_j$ to position $b_j$. A move consists in picking an element $b_j$ at position $a_j$ and moving it to its destination position $b_j$ (the destination hole becomes an unmovable peg). We delete the edge, and proceed to choose the next move which will start from one of the two nearest reachable elements $b_k$ from position $b_j$ (only holes between $b_j$ and $b_k$ are allowed). We must find a sequence of $N$ consecutive moves.

For each $(a_j,b_j)$ consider $b_j$ (at array position $a_j$) as the starting element $start$.

For each $(a_k,b_k), a_k \neq a_j $ consider $a_k$ as the final element $end$ (the edge from position $a_k$ to position $b_k$ will be the final edge).

generate a sequence of moves from $start$ using the following criteria until you reach element $end$ (and a solution has been found), or a stop condition

When you make a move you fix a peg at position $b_j$ and the array is splitted in two partitions $L$ (left) and $R$ (right) and the only way to go from $L$ to $R$ (or from $R$ to $L$) is using an edge that jump across the peg. Set

$edgesLR$ = number of edges from  left to right (do not count the final edge)
$edgesRL$ = number of edges from right to left (do not count the final edge)
$flow$ = $edgesLR - edgesRL$

Cases:

A) if $| flow | > 1$ then one of the two partitions will become unreachable, stop

Now suppose that $end > b_j$, i.e. $end \in R$

B) if $flow = 1$ then there is an extra edge from left to right, you must go left (pick the nearest element of $L$), otherwise you will never reach $end$

C) if $flow = -1$ then there is an extra edge from right to left and whatever node you pick you will never reach $end$, stop

D) if $flow = 0$ you must go right (pick the nearest element of $R$), otherwise you will neve reach $end$

If $end < b_j$ ($end \in L$), B,C,D are inverted.

NOTE: when moving left or right, you must consider $end$ as a peg. For example, if you must go right, but the nearest element on $R$ is $end$ then the move is impossible (and you must proceed with another pair $(start,end)$)

Apply the same resoning at every move.

COMPLEXITY

The flows over each hole can be precalculated in O(N) and reused at every scan.

The loops are:

for start = 1 to N
  for end = 1 to N
    for move = 1 to N
      make a move (fix a peg and update flows)
      check if another move can be done using flow

No choices are made during the computation, so the complexity of the algorithm is $O(N^3)$

CODE

This is a working Java implementation of the algorithm:

public class StrangeSort {
    static int PEG = 0xffffff, HOLE = 0x0;
    static int M = 0, N = 0, choices = 0, aux = 0, end;
    static int problem[][], moves[], edgeflow[], field[];
    boolean is_hole(int x) { return x == HOLE; }
    boolean is_peg(int x) { return x == PEG; }
    boolean is_ele(int x) { return ! is_peg(x) && ! is_hole(x); };
    int []cp(int src[]) { // copy an array
        int res[] = new int[src.length];
        System.arraycopy(src, 0, res, 0, res.length);
        return res;
    }
    /* find the first element on the left (dir=-1) right (dir=1) */
    int find(int pos, int dir, int nm) {
        pos += dir;
        while (pos >= 1 && pos <= M ) {
            int x = field[pos];
            if ( is_peg(x) || (pos == end && nm < N-1) ) return 0;
            if ( is_ele(x) ) return pos;
            pos += dir;
        }
        return 0;
    }
    void build_edges() {
        edgeflow = new int[M+1];
        for (int i = 1; i<=M; i++) {
            int start = i;
            int b = field[start];
            if (! is_ele(b)) continue;
            if (i == end) continue;
            int dir = (b > start)? 1 : -1;
            start += dir;
            while (start != b) { edgeflow[start] += dir; start += dir; }
        }
    }
    boolean rec_solve(int start, int nm) {
        boolean f;
        int j;
        int b = field[start];
        moves[nm++] = b;
        if (nm == N) return true;
        //System.out.println("Processing: " + start + "->" + field[start]);
        field[start] = HOLE;
        field[b] = PEG;
        int dir = (b > start)? 1 : -1;
        int i = start + dir;
        while (i != b) { edgeflow[i] -= dir; i += dir; } // clear edge
        int flow = edgeflow[b];
        if (Math.abs(flow) > 2) return false;
        if (end > b) {
            switch (flow) {
            case 1 :
                j = find(b,-1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            case -1 :
                return false;
            case 0 :
                j = find(b,1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            }
        } else {
            switch (flow) {
            case -1 :
                j = find(b,1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            case 1 :
                return false;
            case 0 :
                j = find(b,-1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            }
        }
        return false;
    }
    boolean solve(int demo[][]) {
        N = demo.length;
        for (int i = 0; i < N; i++)
            M = Math.max(M, Math.max(demo[i][0], demo[i][1]));
        moves = new int[N];
        edgeflow = new int[M+1];
        field = new int[M+1];
        problem = demo;
        for (int i = 0; i < problem.length; i++) {
            int a = problem[i][0];
            int b = problem[i][1];
            if ( a < 1 || b < 1 || a > M || b > M || ! is_hole(field[a]) || ! is_hole(field[b])) {
                System.out.println("Bad input pair (" + a + "," + b + ")");
                return false;
            }
            field[a] = b;
        }
        for (int i = 1; i <= M; i++) {
            end = i;
            build_edges();
            if (!is_ele(field[i])) continue;
            for (int j = 1; j <= M; j++) {
                if (!is_ele(field[j])) continue;
                if (i==j) continue;
                int tmp_edgeflow[] = cp(edgeflow);
                int tmp_field[] = cp(field);
                choices = 0;
                //System.out.println("START: " + j + " " + " END: " + i);
                if (rec_solve(j, 0)) {
                    return true;
                }
                edgeflow = tmp_edgeflow;
                field = tmp_field;
            }
        }
        return false;
    }
    void init(int demo[][]) {

    }
    public static void main(String args[]) {
        /**** THE INPUT ********/

        int demo[][] =  {{4,2},{5,7},{6,3},{10,12},{11,1},{13,8},{14,9}};

        /***********************/
        String r = "";
        StrangeSort sorter = new StrangeSort();
        if (sorter.solve(demo)) {
            for (int i = 0; i < N; i++) { // print it in clear text
                int b =  moves[i];
                for (int j = 0; j < demo.length; j++)
                    if (demo[j][1] == b)
                        r += ((i>0)? " -> " : "") + "(" + demo[j][0] + "," + demo[j][1] + ")";
            }
            r = "SOLUTION: "+r;
        }
        else
            r = "NO SOLUTIONS";
        System.out.println(r);
    }
}


Can you explain an intuition behind Coherent Spaces? Linear Logic is interpreted using Coherent spaces, and they feature prominently in Girard's papers. I know all the three main ways to formally define them, and they don't really pose any problem to use and prove stuff about, but I just can't understand what they mean.

It really feels like there is some kind of a way to understand them. First of all, there're some examples about them which use functions on booleans (like at a wiki somewhere). And it hints at something interesting and meaningful behind the formal definition. However, bool is a very simple coherent space, with no clique of size > 1. Can someone elaborate?

Another thing Girard says somewhere that every point of a coherent space represents a specific "sequence of questions/answers", with two points being coherent if they "bifurcate negatively (i.e., on different questions)", and incoherent if they bifurcate on different answers[1]. It seems like an easy to grasp idea but I just can't invent an example so it means I don't really get it...

Could someone please help me with that?

[1] J-Y Girard, The phantom of transparency. URL: http://iml.univ-mrs.fr/~girard/longo1.pdf

The intuition behind coherence spaces is that the elements of a coherence space represent observations of some underlying data, and the coherence relation tells you whether two observations could have come from the same piece of data.

Concretely, suppose we have a set of animals

Animals = {cat, duck, fish}

Now, we can have a set of observations:

Observations = {warm-blooded, swims, water-breathing, furry}

Let us say that two observations are compatible if they could both be made of the same animal. Every observation is compatible with itself, and in addition:

warm-blooded $\stackrel{{\large\frown}}{{\small\smile}}$ furry
warm-blooded $\stackrel{{\large\frown}}{{\small\smile}}$ swims
warm-blooded $\stackrel{{\large\frown}}{{\small\smile}}$ furry
swims $\stackrel{{\large\frown}}{{\small\smile}}$ water-breathing

We know that being warm-blooded is compatible with swimming, because ducks are both warm-blooded and swim. But being warm-blooded and water-breathing are not compatible, since we have no animals which are both warm-blooded and water-breathing.

At this point, we have defined a coherence space (Observations, $\stackrel{{\large\frown}}{{\small\smile}}$), where Observations is the web, and $\stackrel{{\large\frown}}{{\small\smile}}$ is the coherence relation.


How hard is unshuffling a string? A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPP and SSISI.  Let me call a string square if it is a shuffle of two identical strings. For example, ABCABDCD is square, because it is a shuffle of ABCD and ABCD, but the string ABCDDCBA is not square.

Is there a fast algorithm to determine whether a string is square, or is it NP-hard?  The obvious dynamic programming approach doesn't seem to work.

Even the following special cases appear to be hard: (1) strings in which each character appears at most four six times, and (2) strings with only two distinct characters.  As Per Austrin points out below, the special case where each character occurs at most four times can be reduced to 2SAT.

Update:  This problem has another formulation that may make a hardness proof easier.

Consider a graph G whose vertices are the integers 1 through n; identify each edge with the real interval between its endpoints.  We say that two edges of G are nested if one interval properly contains the other.  For example, the edges (1,5) and (2,3) are nested, but (1,3) and (5,6) are not, and (1,5) and (2,8) are not.  A matching in G is non-nested if no pair of edges is nested.  Is there a fast algorithm to determine whether G has a non-nested perfect matching, or is that problem NP-hard?

Unshuffling a string is equivalent to finding a non-nested perfect matching in a disjoint union of cliques (with edges between equal characters).  In particular, unshuffling a binary string is equivalent to finding a non-nested perfect matching in a disjoint union of two cliques.  But I don't even know if this problem is hard for general graphs, or easy for any interesting classes of graphs.
There is an easy polynomial-time algorithm to find perfect non-crossing matchings.

Update (Jun 24, 2013): The problem is solved!  There are now two independent proofs that identifying square strings is NP-complete.

In November 2012, Sam Buss and Michael Soltys announced a reduction from 3-partition, which shows that the problem is hard even for strings over a 9-character alphabet.  See "Unshuffling a Square is NP-Hard", Journal of Computer System Sciences 2014.
In June 2013, Romeo Rizzi and Stéphane Vialette published a reduction from the longest common subsequence problem.  See "On Recognizing Words That Are Squares for the Shuffle Product", Proc. 8th International Computer Science Symposium in Russia, Springer LNCS 7913, pp. 235–245.

There is also a simpler proof that finding non-nested perfect matchings is NP-hard, due to Shuai Cheng Li and Ming Li in 2009.  See "On two open problems of 2-interval patterns", Theoretical Computer Science 410(24–25):2410–2423, 2009.

Michael Soltys and I have succeeded in proving that the problem of determining whether a string can be written as a square shuffle is NP complete. This applies even over a finite alphabet with only $7$ distinct symbols, although our proof is written for an alphabet with $9$ symbols.  This question is still open for smaller alphabets, say with only $2$ symbols. We have not looked at the problem under the restriction that each symbol appears only $6$ times (or, more generally, a constant number of times); so that question is still open.

The proof uses a reduction from $3$-Partition.  It is too long to post here, but a preprint, "Unshuffling a string is $\text{NP}$-hard", is available from our web pages at:

http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/

and

http://www.cas.mcmaster.ca/~soltys/#Papers.

The paper has been published in the Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X


Lower bounds on batched query search I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a distinct key. We are looking for the value of each key (that is, $v(q _i)$. Noticing that, a set of keys $Q' \subset Q$ may have the same corresponding value [that is, for each $q _i, q _j \in Q' \subset Q, v(q _i) = v (q _j)$].

What is the minimum time complexity to search for the values of all keys in $Q$?

Can it be less then searching individually and sequentially for each $q \in Q$?

N.B: I noticed most research in this field considered sequential files. But what would the answer be if the files was indexed using hash table or B+-tree ?

Example: the database D can be a Domain Name Server .. the queries may be any number of url's ? url's are the keys and the value are the IP addresses .. Some URL's may have the same value ... for instance, google.com and goolgle.com returns the same IP ... [hypothetically]

It depends on how the query is implemented. If we are doing dictionary lookups and we stored the values using cuckoo hashing for example, then each lookup is $O(1)$ time, and doing the lookup in a batch can't possibly improve that run-time. (It takes that long just to list the values).

On the other hand, if we use  a tree based data structure, we may be able to improve the run-time from the $k \cdot Q(n)$ time to perform $k$ queries that each individually take $Q(n)$ time. For example, if the keys are clustered closely together, and we use a finger-search tree. (See e.g. Brodal's chapter on finger search trees).

If you are dealing with sequential files, then
Expressions for Batched Searching of Sequential and Hierarchical Files is a relevant reference.

If you are concerned with the I/O cost of accessing an external database, then perhaps the buffer tree is a more relevant reference.


On the notion of positive rank The positive rank of a square matrix is defined in Theorem $3$ of "Expressing Combinatorial Optimization Problems by Linear Programs" by Mihalis Yannakakis as follows: given a $n\times n$ matrix $A$, the positive rank $rank_{\Bbb R}^+(A)$ is the smallest $m$ such that $A=LR$ for a non-negative $n\times m$ matrix $L$, and non-negative $m\times n$ matrix $R$.

This concept is valuable in communication complexity, since it was shown that if $rank_{\Bbb R}^+(A)$ and $rank_{\Bbb R}(A)$ could be quasi-polynomially related for a $0/1$ matrix $A$, then the log-rank conjecture holds.

Is there an example of a $0/1$ matrix $A$ whose positive rank is strictly smaller than the dimension $m$ of any positive decomposition of $A$ into $0/1$ matrices $L,R$?

I think Theorem 1.1 in http://cjtcs.cs.uchicago.edu/articles/2016/2/cj16-02.pdf answers this.

  Do we know that if non-negative rank and real rank are not quasipolynomially related then the log-rank conjecture fails?

The converse is direct.

This is not an answer, but another version, NOT equivalent to the original of this excellent, but perhaps hard to grasp question.
Define the bipartite clique partition number of a graph as the least number of its complete bipartite subgraphs that cover each edge exactly once.
Similarly define the support of the fractional bipartite clique partition number of a graph as the least number of its complete bipartite subgraphs that have a positive weighing such that for each edge the sum of the weights of the subgraphs containing it is exactly one.
The question is whether these two parameters are always equal or not.

I find it quite surprising that while fractional version are studied a lot, I've never heard of studying the size of the support of the fractional version.
I also wonder whether this latter parameter has any applications.
Also, the question could be asked about several other parameters.


Minimum weights needed to derandomize weight assignment by isolation lemma Under isolation lemma if you have a graph with $2n$ vertices and $m$ edges an isolating weight assignment can be obtained by assigning edges weights randomly from $\{1,2,\dots,2m-1,2m\}$. A weight assignment is isolating if there is an unique perfect matching with minimum sum weight.

Is $\Omega(m)$ weight necessary or would it be possible that there is a (deterministic) scheme that can get the job done in $O(\sqrt m)$?

Note that the best weights we know uses $O(2^m)$.

A deterministic scheme with tiny weights is easy to achieve: first, compute an arbitrary perfect matching, deterministically. Then, give the matched edges weight zero and all other edges weight one. The difficult question is how to compute a deterministic isolating scheme more quickly than finding a perfect matching.


Does NP-hardness imply P-hardness? If a problem is NP-hard (using polynomial time reductions), does that imply that it is P-hard (using log space or NC reductions)?  It seems intuitive that if it is as hard as any problem in NP that it should be as hard as any problem in P, but I don't see how to chain the reductions and get a log space (or NC) reduction.

No such implication is known.  In particular it may be that $L \ne P = NP$ in which case all problems (including trivial ones) are NP-hard under poly-time reductions (as the reduction can just solve the problem), but trivial ones (in particular ones that lie in L) are surely not P-hard under logspace reductions (as otherwise L=P).

The same goes for NC instead of L.


Overlaying a point cloud on a two-dimensional probability distribution such that the local point density corresponds to the local probability density Say I sample a set of points $(p_1,p_2,...) \in P$ from a probability distribution $f(x,y)$, e.g. a bivariate normal distribution, such that my sampling process chooses a point in the distribution with a probability proportional to the value $f(x,y)$ at that point.  In particular, let's say we use the Metropolitan-Hastings algorithm to sample the set of points $P$ via a biased random walk.

Now, I take $P$, and I apply some arbitrary geometric rotational and translational geometric transform that acts uniformly on all points $p_i \in P$.  I provide this transformed set of points $P^*$ to you, and your job is to reverse the geometric transform and map the coordinates back to their original positions to the best of your ability.

What is the optimal way to proceed?

A thought is that we can sample a new set of points $P_2$ from the distribution $f(x,y)$, and then use something like the RANSAC algorithm (http://en.wikipedia.org/wiki/RANSAC) to find a geometric transform to align the $P^*$ and $P_2$.  This, however, seems to be a bit wasteful?

Motivation - Say we know that the maxima of the distribution $f(x,y)$ occurs at some $(x_k,y_k)$.  What is $(x_k,y_k)^*$, i.e. where is this point after applying the geometric transform that mapped $P$ to $P^*$?  We could also ask about other "distinct" points of interest in $f(x,y)$ so that it isn't simply a matter of computing something like a geometric mean (or perhaps geometric median) of the point set $P^*$ to calculate $(x_k,y_k)^*$.  Can we figure this out without the kind of silly solution I propose the employs the RANSAC algorithm?

(In response to R. B.'s comments): I mean "up to symmetry" here - apologies for the confusion.

Overlaying a point cloud on a two-dimensional probability distribution such that the local point density corresponds to the local probability density is a good way to define the cell generators of a centroidal Voronoi tessellation (CVT).

CVTs don't loose their quantization precision by translation or rotation in concert with the underlying probability distribution. Not sure what your question is.


Learning a coin's bias (localized) It's well known that the minimax sample complexity for estimating the bias $p$ of a coin to additive error $\epsilon$ with confidence $\delta$ is
$\Theta(\epsilon^{-2}\log(1/\delta))$. What if we know that $p$ lies in some specified range, say $[p_0-\eta,p_0+\eta]$ -- is the minimax sample complexity known in terms of $p_0$ and $\eta$? Note that $p_0=\eta=1/2$ recovers the general setting as a special case.

Write $p=p_0=1-q$. We may assume that $\epsilon<\eta \le p\le 1/2$. Then the sample complexity is of order $\log(1/\delta)$ times the reciprocal of the relative entropy  $D((p,q)||(p+\epsilon,q-\epsilon))$.
This yields sample complexity  $\Theta(p\epsilon^{-2}\log(1/\delta))$.


Instances of Noninteractive Zero knowlege Proofs I am working on Cryptographic protocols. While I was doing a survey, I required some "Non-Interactive Zero Knowledge Proofs" (NIZK) which I can use.

I can only find transformations between different models of NIZK in the abstract sense, like the Hidden Bits Model (J.Katz) and non-malleable NIZK (A.Sahai)

Is there any credible material like Thesis/Papers where I can find example constructions of Non-Interactive Zero Knowledge Proofs which I can make use for my protocols.

Thanks!

I'm not sure what exactly you are looking for.

Goldreich's book ("Foundations of Cryptography, volume 1") contains an extensive discussion of non-interactive ZK proofs. So do these lecture notes of Katz (lectures 11-13): http://www.cs.umd.edu/~jkatz/gradcrypto2/scribes.html.

You could also look at this paper: Uriel Feige, Dror Lapidot, Adi Shamir: Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions. SIAM J. Comput. 29(1): 1-28 (1999) and references therein.


Batch membership testing for convex polyhedron specified in vertex representation I have a convex shape defined by a set of vertices (the so-called vertex representation of a convex polyhedron). I also have a large set of points and I would like to test which are contained in the convex shape.  Currently I just use an open source linear programming solver for each point independently with a constant objective function.

However this is quite slow even in 100 dimensions.  Is there a way to use the fact that all the query points are known in advance to speed the process up?

Instead of testing each point individually whether it is contained in the convex polyhedron, you should search for a supporting hyperplane of the polyhedron which separates the point from the polyhedron. If a supporting hyperplane does not exists, you know that the point is contained in the polyhedron. Otherwise, the supporting hyperplane helps you to separate additional points from the polyhedron. This is similar to the idea of D.W. but here you only enumerate a smaller number of supporting hyperplanes which is sufficient to separate all outer points.

Here are the details: Let $V$ be a matrix whose columns are the vertices $\mathbf{v}_1,\dots,\mathbf{v}_k$ of the polyhedron $\mathbf{P}$. The test points are denoted by $\mathbf{w}_1,\dots,\mathbf{w}_l$. A hyperplane $\{\mathbf{x}\mid \mathbf{n}^T\mathbf{x} = \lambda\}$ separates $\mathbf{P}$ and some point $\mathbf{w}_j$ if and only if $\mathbf{n}^T\mathbf{v}_i \leq \lambda$ for all $i=1,\dots,k$ and there is some positive $\epsilon>0$ with $\mathbf{n}^T\mathbf{w}_j \geq \lambda+\epsilon$. Assume, such an $\epsilon$ exists, then the conditions above are equivalent to
$\frac{1}{\epsilon}\mathbf{n}^T\mathbf{v}_i - \frac{1}{\epsilon}\lambda \leq 0$ for all $i=1,\dots,k$ and $\frac{1}{\epsilon}\mathbf{n}^T\mathbf{w}_j - \frac{1}{\epsilon}\lambda \geq 1$.
Substituting $\frac{1}{\epsilon}\mathbf{n}$ by $\tilde{\mathbf{n}}$ and $\frac{1}{\epsilon}\lambda$ by $\tilde{\lambda}$ yields the system of linear inequalities
$$V\tilde{\mathbf{n}} - \mathbf{1}\tilde{\lambda} \leq 0,\quad \mathbf{w}_j^T\tilde{\mathbf{n}} - \tilde{\lambda} \geq 1$$
where $\mathbf{1}$ is the vector whose coefficients are all $1$. Hence, the linear program
$$\mbox{minimize } \lambda \mbox{ subject to } V\mathbf{n} - \mathbf{1}\lambda \leq 0,\ \mathbf{w}_j^T\mathbf{n} - \lambda \geq 1$$
is either infeasible and $\mathbf{w}_j$ is contained in $\mathbf{P}$ or its  optimal solution $(\lambda, \mathbf{n})$ provides a separating hyperplane, which is indeed a supporting hyperplane of $\mathbf{P}$. Each remaining point $\mathbf{w}_i$ with $\mathbf{n}^T\mathbf{w}_i > \lambda$ is also not contained in $\mathbf{P}$ and can be removed from the test set.


Problems that are counter-intuitively solvable in practice? Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in algorithms or complexity before. Not surprisingly, a lot of notions seemed strange at first but made sense with some examples (PTIME, intractability, uncomputability), while others seem to come more natural (problem classification via reductions, time and space as resources, asymptotic analysis). Everything was going great until I accidentally admitted that SAT can be solved efficiently* in practice... And just like that, I lost them. It didn't matter how convincingly I was trying to argue for theory, the kid was convinced that it was all artificial crap math that he should not care for. Well...

¯\_(ツ)_/¯

No, I was not heart-broken, nor did I really care about what he thought, that's not the point of this question. Our conversation had me thinking of a different question,

  How much do I really know about problems that are theoretically
  intractable (superpolynomial time complexity) but practically
  solvable (via heuristics, approximations, SAT-solvers etc.)?

I realized, not much. I know that there are some very efficient SAT-solvers that solve enormous instances efficiently, that Simplex works great in practice, and maybe a few more problems or algorithms. Can you help me paint a more complete picture? Which well-known problems or even classes of problems are in this category?

TL;DR: What are problems that are counter-intuitively solvable in practice? Is there an (updated) resource to read more? Do we have a characterization for them? And, finally, as a general discussion question, shouldn't we?

EDIT #1: In trying to answer my last discussion question about such a characterization, I was introduced to smoothed analysis of algorithms, a concept introduced by Daniel Spielman and Shang-Hua Teng in [1] that continuously interpolates between the worst-case and average-case analyses of algorithms. It is not exactly the characterization discussed above, but it captures the same concept, and I found it interesting.

[1] Spielman, Daniel A., and Shang-Hua Teng. "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time." Journal of the ACM (JACM) 51, no. 3 (2004): 385-463.

Highly structured SAT instances (even on millions of variables) can often be solved in practice. However, random SAT instances near the satisfiability threshold with even a few hundred variables are still open (meaning, even in practice, if you generate such a thing you may never know in the lifetime of the universe whether the thing you generated is satisfiable or not using current SAT solvers). You might be interested in this related question and its answers.
Clique finders are also shockingly good "in practice"

With respect to clique finders, (part of the) explanation is given
by an average case analisys of the algorithms in question.

See https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub

Integer programming and mixed integer-linear programming (with some rational and some integer variables) are the focus of whole Operations Research departments, and can often (but not always) be solved in practice
From what I understand, many $\mathsf{PSPACE}$-complete problems that arise in verification can often be solved in practice, but "in practice" usually implies "on highly structured instances". (In contrast, we still don't know who wins for pretty small instances of the game of Go, which is another $\mathsf{PSPACE}$-complete problem.)
Many problems in computational algebraic geometry can be solved in practice on small instances using Grobner bases, but these fail miserably on larger instances, or even small instances that have high "complexity" (as measured by the Castelnuovo-Mumford regularity). And these problems are even $\mathsf{EXPSPACE}$-complete!
As already pointed out in the comments by D. W., Graph Isomorphism can pretty much be solved in practice. It is very hard to stump modern GI software such as nauty, bliss, saucy, etc.


PageRank for a Non-Random Searcher I'm looking to adapt the PageRank algorithm as a centrality measure in a network. This network however, unlike the "random surfer" of the original paper on PageRank, or the random library browser for Eigenfactor.org, doesn't have a random browser who can leave and jump off to some other network. The theoretical reader is reading only this literature, and reading it completely.

As I understand it, the damping factor in the usual implementation of PageRank is 1 - probability of the random surfer jumping to a different site, and is usually set at 0.85. Is it reasonable then, in an entirely closed network, to set this value = 1.0, or is there something I'm not seeing?

Some details of the network, which would probably be helpful:

All the networks I will be looking at are fairly small, less than 1000 nodes, and directed. They're citation networks - with papers as nodes and edges as citations between papers, so inherently there are no isolated nodes not connected to any other nodes, as their inclusion in the network is conditional on there being a link to or from the network. There's no reason to believe the network is strongly connected - indeed, I'm pretty sure they're inherently not.

Let $\alpha$ be the probability of clicking through a link and let $1-\alpha$ be the probability of going to a random website. I think you're asking whether PageRank will work with $\alpha=1$. The answer is yes if and only if the network is strongly connected and the induced random walk is aperiodic. I'm not sure what "entirely closed" means.

Setting $\alpha = 1 $ gives intuition for how PageRank works, but there are very good reasons for setting $\alpha < 1$. Namely, we want PageRank (1) to converge in every graph, (2) to converge to the same thing regardless of the initial rank distribution, (3) to converge as quickly as possible. PageRank is just a fancy name for how to set up a particular Markov Chain. For any $\alpha \in [0,1] $ you'll get some Markov Chain, you just need to make sure that it has properties 1-3.

This is the best PageRank survey that I've seen (better than Wikipedia or the original paper) and explains this: http://www.ams.org/samplings/feature-column/fcarc-pagerank

Edit: As per MCH's answer we also want the 4th condition that every vertex has positive rank, which is also ensured by the random surfer model.


What are different definitions of Universal Turing-machine? I am not sure what is the appropriate way for this, but I would like to collect different possible definitions/variants of Universal Turing-machines.
Here are the ones I know, post below if you know other definitions/comments/don't agree.
For simplicity, I assume that we talk about two-tape machines with alphabet {0,1,*}, but let me know if in some definition this might make a difference.
I denote by T(x,..,z) the output of Turing-machine T when the inputs on its tapes are x,..,z, if it halts, and "running forever" otherwise.

Exists. U is universal if for every T there is a p such that for every x we have U(p,x)=T(x).

Computable. U is universal if there is a computable encoding E of Turing-machines (labeled directed graphs) into strings such that for every T and x we have U(E(T),x)=T(x).

Fix. Fix a (computable) encoding E of Turing-machines into strings. U is universal if for every T and x we have U(E(T),x)=T(x).

Strict. In both the Computable and the Fix definition, we can also demand that for every input that is not of the above format, U does nothing useful (halts without output, outputs the empty string, or runs forever).

I found some alternate definitions of Universal Turing Machine in papers related to the universality of small Turing machines and other models.

See for example the four definitions (the first 3 are equivalent and are similar to yours except that there there is also an explicit decoding function) in section 2 of Yurii Rogozhin, Small universal Turing machines, Theoretical Computer Science, Volume 168, Issue 2, 20 November 1996, Pages 215-240.

For example the Davis's definition in M. D. Davis, A Note on Universal Turing Machines ; Martin Davis, The Definition of Universal Turing Machine . Journal of Symbolic Logic 35 (1970), no. 4, 590; bypasses the encoding phase:

A generic machine (Turing machine, tag-system, ...) is universal if and only if its halting problem is r.e. complete.

Probably you're not interested in them (and you'll probably know them), but there are also  notions of semi-weakly universal  and weakly universal Turing machines (in which the initial tape has an infinite repeated string on the left/right/left+right of the input). For further details see the work of Neary and Woods on small TMs.


Is `sort` typeable on elementary affine logic? The following λ-term, here in normal form:

sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l))
       (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j
       (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c))

Implements a sorting algorithm for church-encoded lists. That is, the result of:

sort (λ c n . (c 3 (c 1 (c 2 n)))) β→ (λ c n . (c 1 (c 2 (c 3 n))))

Similarly,

sort_below = λabcd.a(λef.f(λghi.g(λj.h(λkl.kj(ikl)))(hi))e(λgh.h))
            (λe.d)(λe.b(λf.e(f(λghi.hg)(λgh.cfh))))

Also implements sorting for the same lists as above, except you must provide an additional argument with a limit for the numbers it will consider:

sort_below 4 [5,1,3,2,4] → [1,2,3]

I am trying to determine whether those terms are typeable on elementary affine logic. Since I don't know any EAL type-checker publicly available, this is proving a harder task than I expected. Is there a type for sort in elementary affine logic?

I think sort, as presented there, isn't typeable on EAL. I can't prove that, but it doesn't work on Lamping's Abstract Algorithm without the oracle. Moreover, while the term is somewhat clever and brief, it uses very wacky strategies that are not EAL-friendly.

But behind this question there is a more interesting one: "can a nat-sorting function be implemented in EAL"? That was a very hard question back then, but now it looks pretty trivial. Yes, of course. There are many simpler ways to do it. For an example, one can just fill a Scott-encoded NatSet with Church-encoded Nats, and then convert it to a list. Here is a complete demonstration:

-- sort_example.mel
-- Sorting a list of Church-encoded numbers on the untyped lambda calculus
-- with terms that can be executed by Lamping's Abstract Algorithm without
-- using the Oracle. Test by calling `mel sort_example.mel`, using Caramel,
-- from https://github.com/maiavictor/caramel

-- Constructors for Church-encoded Lists
-- Haskell: `data List = Cons a (List a) | Nil`
Cons head tail = (cons nil -> (cons head (tail cons nil)))
Nil            = (cons nil -> nil)

-- Constructors for Church-encoded Nats
-- Haskell: `data Nat = Succ Nat | Zero`
Succ pred = (succ zero -> (succ (pred succ zero)))
Zero      = (succ zero -> zero)

---- Constructors for Scott-encoded NatMaps
---- Those work like lists, where `Yep` constructors mean
---- there is a number on that index, `Nah` constructors
---- mean there isn't, and `End` ends the list.
---- Haskell: `data NatMap = Yep NatMap | Nah NatMap | End`
Yep natMap = (yep nah end -> (yep natMap))
Nah natMap = (yep nah end -> (nah natMap))
End        = (yep nah end -> end)

---- insert :: Nat (Church) -> NatMap (Scott) -> NatMap (Scott)
---- Inserts a Church-encoded Nat into a Scott-encoded NatMap.
insert nat natMap    = (nat succ zero natMap)
    succ pred natMap = (natMap yep? nah? end?)
        yep? natMap  = (Yep (pred natMap))
        nah? natMap  = (Nah (pred natMap))
        end?         = (Nah (pred natMap))
    zero natMap      = (natMap Yep Yep (Yep End))

---- toList :: NatMap (Scott) -> List Nat (Church)
---- Converts a Scott-Encoded NatMap to a Church-encoded List
toList natMap        = (go go natMap 0)
    go go natMap nat = (natMap yep? nah? end?)
        yep? natMap  = (Cons nat (go go natMap (Succ nat)))
        nah? natMap  = (go go natMap (Succ nat))
        end?         = Nil

---- sort :: List Nat (Church) -> List Nat (Church)
---- Sorts a Church-encoded list of Nats in ascending order.
sort nats = (toList (nats insert End))

-- Test
main = (sort [1,4,5,2,3])

Here is the bruijn-indexed normal form of a slightly altered version of the sort above, which must receive (x -> (x x)) as the first argument in order to work (otherwise it doesn't have a normal form):

λλ(((1 λλλ(((1 λλλ((1 3) (((((5 5) 2) λλ(1 ((5 1) 0))) 1) 0)))
λ(((3 3) 0) λλ(1 ((3 1) 0)))) λλ0)) ((0 λλ(((1 λλ(((0 λλλλ(2 (
5 3))) λλλλ(1 (5 3))) λλλ(1 (4 3)))) λ(((0 λλλλ(2 3)) λλλλ(2 3
)) λλλ(2 λλλ0))) 0)) λλλ0)) λλ0)

Pretty simple in retrospect.


The Dyck Language Correction Problem Given a word $w$ over $\{ [, ] \}$, the alphabet of the two square brackets, the Dyck correction problem is to find the shortest sequence of edit operations that would make $w$ a Dyck word, i.e., a word in which the squared brackets are balanced.
I can imagine a few practical applications, but my bibliography search yielded nothing. It looks like dynamic programming though. Any ideas?

The generalized problem, concerning Dyck($s$), for $s$ distinct pairs of parenthesis, was studied by Barna Saha in a paper entitled The Dyck Language Edit Distance Problem in Near-linear Time
B. Saha, "The Dyck Language Edit Distance Problem in Near-Linear Time," 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, USA, 2014, pp. 611-620, doi: 10.1109/FOCS.2014.71.
Indeed, the problem is easy for $s=1$. For $s\ge2$ the exact complexity is not known. The classical techniques for correcting context-free languages are $O(sn^3)$ (Valiant 1975). On the other hand, the usual string editing problem which can be solved in quadratic time can be reduced to Dyck($s$).
Saha's result gives a nearly linear time algorithm that returns an approximation of the true edit distance. I am not sure whether this algorithm can produce the edit sequence.


Entscheidungsproblem vs. Unvollständigkeitssatz (soft question) The first term is used by Hilbert in his 1928 work, but in Gödel's later work, the same thing is referred to as Unvollständigkeitssatz ("incompleteness theorem"). For today's German CS researchers, it seems Unvollständigkeitssatz is more commonly used, and Entscheidungsproblem ("decision problem") is still understood, but not necessarily associated with das Halteproblem (which seems to be more common after Turing's work on automata). On the other hand, for English CS researchers, Entscheidungsproblem is usually the only word they are familiar with.

Note: the words are not the same, and it could be argued that Hilbert's question about deciding was answered in the negative for a particular case by Gödel's statements about incompleteness, so that incompleteness demolishes decision in general.

Interestingly, when looking at the German Wikipedia, there is no entry for Entscheidungsproblem, but there is one for Gödelscher Unvollständigkeitssatz, and the entry about Hilbert uses Gödelscher Unvollständigkeitssatz. When looking at the English Wikipedia, one readily finds an entry for Entscheidungsproblem.

How come Entscheidungsproblem is no longer used in German?

The two words do not refer to the same thing. Hilbert's Entscheidungsproblem was the question whether there is an algorithm that decides the universal truth of first-order logical sentences, which was answered negatively by Turing in his famous 1936 paper "On Computable Numbers, with an application to the Entscheidungsproblem". The word literally means decision problem. I assume that the word is no longer used since it refers to a problem that has been solved. In English it may still be more common due to its prominent use in the title of Turing's paper.

Gödels Unvollständigkeitssatz is his incompleteness theorem, stating that no consistent arithmetic theory is complete, in particular it can not prove its own consistency. This answered negatively a different question of Hilbert, viz. the second of his 23 famous problems, which was to prove the consistency of the axioms of arithmetic.


(How) can you model broadcasts in the pi-calculus? Can you model reliable broadcasts in the pi-calculus?

If so: How?

If not: Are there any similar process algebras where you can?

What I have tried:

If sender $S$ wants to send a message $y$ to all $P_1$ to $P_n$, you could write
!($\overline{x}y).S$ and $x(z).P_1$ to $x(z).P_n$. But how do you guarantee that $(\overline{x}y)$ is replicated $n$ times, i.e. no messages get lost?
I do not know $n$ in advance. Is it (only) possible with sending several messages back and forth between all processes involved?

...or do I misunderstand the nondeterministic behavior of replication?

About a decade ago, Ene and Muntean showed that broadcasting has no reasonable compositional encoding into the $\pi$-calculus [1]. The essence of their separation between point-to-point communication and message passing is easy to understand: point-to-point is "too asynchronous". That means that in a broadcasting system, a broadcasting sender can send to $n$ processes in one atomic step for arbitrary $n$. OTOH, if a process wants to communicate with $n$ processes using point-to-point communication, this can only be done using $n$ (or more) separate message exchanges, which have intermediate states (e.g. the sender has sent messages to 100 receivers, and needs to send another 150). A context can observe, interact and interfere with these intermediate states, which is not possible with the atomic broadcast messages. To deal with this shortcoming of $\pi$-calculus (or indeed any calculus based on point-to-point message passing), Ene and Muntean propose a broadcasting variant b$\pi$ [2, 3], based on earlier work by Prasad on CBS, a variant of CCS with broadcasting [4].

More technically, [1] calls an encoding $e$ reasonable if the following is the case.

The encoding preserves parallel composition, i.e. $e(P|Q) = e(P) | e(Q)$.
The encoding preserves injective renaming, i.e. $e(P\sigma) = e(P)\sigma$
for any injective renaming $\sigma$.
The encoding satisfies some technical conditions about the preservation of input and output actions, see [1] for details.

Then [1] shows that no reasonable encoding from b$\pi$ to $\pi$ can exist. They establish this separation result using a variant of Palamidessi's electoral systems proof technique [5].

There has been work on this subject since [1-4] were published, e.g. by M. Hennessy, but those are the pioneering papers.

As an aside, broadcast is usually understood as one sender communicating with many receivers, but it is also possible to generalise point-to-point communication in the other direction where you have one receiver synchronising with multiple senders (this is used in e.g. Petri nets), or hybrid forms of both. I. Phillips has established a separation result that shows that this form of broadcasting can also not be encoded in  $\pi$-calculus. I am not sure whether this result is published or not.

[1] C. Ene, T. Muntean, Expressiveness of Point-to-Point versus Broadcast Communications.

[2] C. Ene, T. Muntean, A Broadcast-based Calculus for Communicating Systems.

[3] C. Ene, T. Muntean, Testing theories for Broadcasting Processes.

[4] K. V. S. Prasad, A Calculus of Broadcasting Systems.

[5] C. Palamidessi, Comparing the Expressive Power of the Synchronous and the Asynchronous $\pi$-calculi.


Approximation algorithms for the maximum $2$-independence set problem I am interested in approximating the maximum $2$-independent set problem in arbitrary graphs. In a graph $G$ a set $I$ of vertices is called $2$-independent if the distance between any two distinct vertices in $I$ is more than $2$. In other words $I$ is $2$-independent in $G$ if and only if $I$ is independent in $G^2$, the square of $G$. $2$-independent sets are also sometimes called $2$-packings, packings or closed neighborhood packings.

The maximum $2$-independent set problems ask for the $2$-independence set with maximum cardinality in a given graphs $G$. In [1] it is proved that for any $\epsilon > 0$ it can't be approximated with a better than $O(n^{1/2-\epsilon})$ multiplicative factor (this problem is called maximum distance-$3$ independent set in this paper). However, I did not find any positive results about its approximation. Is there any $O(\sqrt{n})$-approximation (or worse) algorithm? Or, maybe, there are better inapproximability results?

Also, any results about characterization of the squares of all graphs may help (let us denote the class of squares of all graphs as $\mathcal{G}^{(2)}$). For example, it may occur that $\mathcal{G}^{(2)}$ is a subclass of some class where maximum independent set problem admits some approximation. Or, conversely, it may be a superclass of some class with no approximation better than $n^{1-\epsilon}$. Unfortunately, I am not aware of any such results.

[1] Eto, Hiroshi and Guo, Fengrui and Miyano, Eiji. Distance-$d$ Independent Set Problems for Bipartite and Chordal Graphs // Combinatorial Optimization and Applications, Vol. 7402 (2012), pages 234-244.

An $O(\sqrt n)$-approximation greedy algorithm for this problem is presented in the paper "Independent sets with domination constraints" by Magnús M. Halldórsson, Jan Kratochvı́l, Jan Arne Tellec (Discrete Applied Mathematics, Vol. 99, Issues 1–3, Pages 39–54). The algorithm is greedy: it consequently selects to the output solution a vertex with minimum degree, such that the output solution is still $2$-independent. Thus, the lower and the upper bounds for this problem coincide.