Candidates for One-Way Function Why are the candidates for one-way functions so few?

Today, almost all candidates are based on elementary mathematics, except Goldreich's candidate 2000 and ... (?!).

Why one can not generate several candidates by using advanced mathematics, for example using complex structures of combinatorics?

Here is a "canned" answer that might be useful, but has no cryptographic depth (hopefully we get answers with depth as well).

What makes for a good candidate OWF? The naive answer tends to boil down to "something that looks hard to invert to me", but the expert's response is usually more like "something that many smart people have tried to invert but failed" (or something whose invertability would imply that of such a function). From this perspective, it is worse for the problem to be more obscure (fewer have tried it), and it may be worse that the function is more complicated (this obfuscates whether it is truly difficult or you just cannot see the solution yourself).

To put the intuition another way, a common "bad intuition" is that if a problem looks more complicated or difficult to define/understand, then it is more likely to be computationally difficult to solve. Theoretical crypto does not accept this premise. The primary evidence we have for computational hardness is a history of failed attempts, which means good candidates should be simple, well-known functions with long histories.

the conjecture that (roughly) "every NP complete function could somehow be used to create one way functions" has not been disproven so there is not really a shortage of "candidates" in at least that sense. an interesting recent formulation of this is by Cook et al, On the One-Way Function Candidate Proposed by Goldreich where they analyze the complexity of Goldreich's function by reducing it to SAT and doing empirical SAT experiments which give circumstantial evidence of its hardness (along with theoretical evidence also).

also existence of one way functions is tightly coupled to core long open problems in complexity theory eg the P=?NP problem. which is in turn tightly coupled with proving lower bounds in complexity theory, referred to by Arora/Barak in Complexity theory: a modern approach as complexity theory's Waterloo.

here is one ref by leading researchers on this angle that may be helpful:

On Basing One-Way Functions on NP-Hardness Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz


Is there a name for a hashtable with a tree for each bin instead of a list? It is well-known that the worst case performance for a chaining hashtable, is O(n), where n is the number of objects in the table. The normal assumption is that the hash is either uniform, or secure, however this is not always the case.

One possible solution to this problem would be to use a tree, or other O($\log n$) data structure, instead of the list. This would result in the worst-case performance of O($\log n$) for insertion and retrieval, at the expense of adding an extra constraint on the import data, namely that it would need to be comparable.

Is there a name for such a data structure?

Yes, there is a name for it: Hashtable.

You can have whatever you want for collision bins: Lists, trees, hashtables, whatever you fancy.

You might want to take a look at Judy arrays:

http://en.wikipedia.org/wiki/Judy_array

http://judy.sourceforge.net/


How common is phase transition in NP-complete problems? It is well known that many NP-complete problems exhibit phase transition. I am interested here in phase transition with respect to containment in the language, rather than the hardness of the input, relative to an algorithm.

To make the concept unambiguous, let us formally define it as follows. A language $L$ exhibits phase transition (with respect to containment), if

There is an order parameter $r(x)$, which is a polynomial time computable, real valued function of the instance.
There is a threshold $t$. It is either a real constant, or it may possibly depend on $n=|x|$, that is, $t=t(n)$.
For almost every $x$ with $r(x)<t$, we have $x\in L$. (Almost every means here: all but vanishingly many, that is, the proportion approaches 1, as $n\rightarrow\infty$).
For almost every $x$ with $r(x)>t$, we have $x\notin L$.
For almost every $x$, it holds that $r(x)\neq t$.  (That is, the transitional region is "narrow.")

Many natural NP-complete problems exhibit phase transition in this sense. Examples are numerous variants of SAT, all monotone graph properties, various constraint satisfaction problems,  and probably many others.

Question: Which are some "nice" exceptions? Is there a natural NP-complete problem, which (probably) does not have a phase transition in the above sense?

expert researchers in this area basically assert that phase transitions are a universal feature of NP complete problems although this has yet to be formulated/ proven rigorously and it is not yet widely regarded/ disseminated in the larger field (it emanates more from an empirical-oriented branch of study). its nearly an open conjecture. there is strong evidence. there are no plausible candidates for non phase-transition NP complete problems. here are two refs that support this pov:

Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science / Moore
Phase transition behavior / Walsh (ppt)

here is a rough sketch of the truth of the assertion. it has to do with P contained in NP complete. an NP complete problem/ language must have instances that are solvable in P time and others that are solvable in exponential (or at least superpolynomial-) time if P≠NP. but there must always be some way to "group" the P instances from the "non-P" instances. therefore there must also always be some "transition criteria" between the P and non-P instances. in short, maybe this phenomenon is intrisically coupled with P≠NP!

another rough argument: all NP complete problems are interchangeable via reductions. if a phase transition is found in a single one, it must be found in all of them.

more circumstantial evidence for this, more recently (~2010) it was shown the phase transition shows up for lower bounds on monotone circuits for clique-detection on random graphs.

Average case complexity of detecting cliques / Rossman

full disclosure: Moshe Vardi has studied phase transitions particularly in SAT and has a contrasting more skeptical view in this talk/ video.

Phase transitions and computational complexity

C coloring of D regular graphs have a series of Discrete transitions, not particularly phased, unless you stretch.

Here is a table of coloring results, that I will be submitting to SAT17.  Note that 3 coloring of 6 regular graphs is impossible except for a few examples.  Likewise 4 coloring of tenth degree graphs...  C3D5N180 graphs are mildly difficult.  The C4D9 Golden Point is only tentatively at C4D9N180;  C4D9 graphs are the hardest 4cnfs by size that I have encountered, so C4D9 qualifies as a "Hard Spot".  The C5D16 Golden point is conjectured to exist, but would be in the hard spot region from 5 coloring to 6 coloring.

          Universal Constants of Regular Graph Coloring

Coloring formulas have lgC variables per vertex, for a total of lgC*N variables;
edges have C coloring clauses, for a total of C*M clauses.  There are a few
additional clauses per vertex to rule out extra colors.  The Golden Points are
the smallest N such that: C colorability on degree D graphs with N vertices is
almost always satisfiable, with probability close to 1. For High Probability,
N random instances were satisfiable.  For Very High, N*N were satisfiable.
For Super High, N*N*N random instances were satisfiable.

The High Probability (1 - 1/N) golden coloring points are:

C3D5N180  C4D6N18  C4D7N35  C4D8N60  C4D9N180? C5D10N25  C5D11N42  C5D12N72

The Very High Probability (1 - 1/(N*N)) golden coloring points are:

C3D5N230? C4D6N18  C4D7N36  C4D8N68  C4D9N???  C5D10N32  C5D11N50  C5D12N78

The Super High Probability (1 - 1/(N*N*N)) golden coloring points are:

C3D5N???  C4D6N22  C4D7N58  C4D8N72? C4D9N???  C5D10N38  C5D11N58  C5D12N??

All random instances in the study were satisfiable.
The linear probability points checked hundreds of satisfiable formulas.
The quadratic probability points checked tens of thousands of satisfiable formulas.
The cubic probability points checked hundreds of thousands of satisfiable formulas.
The C4D9 and C5D13 points are difficult.  The C5D16 point is conjectured to exist.
One five colorable sixteenth degree random instance would prove the conjecture.


Finding the Length of the shortest Accepting path of a NDTM Let $M$ be a NDTM (non deterministic Turing machine) which decides a certain NP-complete language, say SAT.

$M$ computes any instance $I$ of the NP-complete problem in at most $p(n)$ non deterministic steps ($p$ in a polynomial function, $n$ is the input size). The length of a computation path can be measured as the "rank" of the non deterministic step where $M$ halts. Let call $rank_M(I)$  the rank of the shortest accepting path ($rank_M(I)$ is $p(n)+1$ if $M$ rejects $I$).

Is this problem NP-complete : Given a boolean expression $I$, is it true that $rank_M(I)=k$ ? ($k$ is polynomially bounded in $n$)

Edit --- $rank_M(I)$ has been modified : it defines now the shortest accepting path (instead of just the rank of the step where $M$ halts).

Thank you.

Your problem is $\mathsf{NP}$-complete, and you can find a proof for instance here (I gave a sketch in comments).

A remark: If you consider $\{\langle M,x,t\rangle : M$ halts on $x$ in $t$ steps $\}$, then you can only show it is $\mathsf{NP}$-hard. But as you mention that you consider $t$ polynomially bounded (in the sizes of $M$ and $x$, I guess), then your problem belongs to $\mathsf{NP}$.

see also thm 5.15 p61 of Hastad's Complexity Theory:

Given a set $A,$ then $A \in \mathsf{NP}$ iff there is a language $B \in \mathsf{P}$
and a constant $k$ such that

$x \in A \Leftrightarrow \exists_{y,|y|\leq|x|^ k}(x, y) \in B$


Algorithm to Determine if (Union of Cartesian Products of Subsets) equals (Cartesian Product of Full Sets) I have already asked this question in StackOverflow (open bounty closing on Aug 25th).

Let's say I have some finite sets: A, B, ..., K

I also have A1, A2, ... An, which are subsets of A; B1, B2, ... Bn, which are subsets of B, etc.

Let's say S is the cartesian product A x B x ... x K

and Sn is the cartesian product of An x Bn x ... x Kn

Is there an algorithm to efficiently determine if the union of all Sn is equivalent to S?

Some pointers to literature where I can study this problem are greatly appreciated.

The problem is coNP-complete and so unlikely to have a poly-time algorithm.  (I'm sure the observation was made before; I don't know where, but look in Garey-Johnson.)

Here is a simple reduction from 3-UNSAT $= \{\psi: \psi$ is an unsatisfiable 3-CNF$\}$.

Say $\psi(x_1, \ldots, x_t) = \bigwedge_{j = 1}^m (y_{j, 1}\vee y_{j, 2} \vee y_{j, 3})$, where
each $y_{j, a}$ is either a variable or a negated variable.

In your notation, let $A = B = \ldots = K = \{0, 1\}$, with $t$ such sets (one for each variable).  Think of each element of $S = A^t$ as an assignment to $x_1, \ldots, x_t$.  For each $j \in [m]$, create a Cartesian product set $S_j$ which describes the set of assignments that will falsify the $j^{th}$ clause.  Note that this can easily be done: we restrict precisely the 3 components corresponding to the variables appearing in this clause.

The union of the $S_j$'s equals all of $S = \{0, 1\}^t$ iff every assignment to $\psi$ falsifies some clause, i.e., iff $\psi$ is unsatisfiable.

Simple observation, lets use {Animal}{Mineral}{Vegetable}

S = A,B,K = {horse,cat,dog}{gold,silver,quartz}{corn,tree, peach}

$S_{0}$ ={horse}{gold}{peach}

$S_{1}$ ={cat}{gold}{peach}

$S_{2}$ ={cat}{gold}{tree} ...

Your $n$ can be as big as $|A|$*$|B|$*$|C|$* ... *$|K|$. That's not tractable.

An adversary can just start generating you random elements in S. Kolomogrov complexity implies you will be forced to store them all without any compression until you get to that intractable number; making your storage intractable.


Polynomial Time Algorithm for Graph Isomorphism Testing "Michael I. Troﬁmov" claims that he has found a poly-time algorithm for graph isomorphism, which works for all graphs.

The paper is given in arXiv. The companion website gives a proof-of-concept program which runs the algorithm. (The password for the program is given in the paper.)

I wanted to know whether the community is aware of Troﬁmov's results, and whether it's been proved, refuted, or unresolved?

For some more discussion of this particular paper, see this thread on a related Wikipedia talk page. Some of the participants in that discussion found specific bugs, and the paper does not seem to have been updated in response. I tried to read it myself but rather than finding any specific bugs I just got lost in vague descriptions of matrices and matrix manipulations that did not make clear which variables were inputs and which were outputs. Based on that experience I don't think the paper should be taken seriously until it's passed some level of peer review (accepted to one of the usual journals or conferences).

More generally, it is easy to define algorithms for graph isomorphism that attempt to amplify some sort of subtle asymmetry in the graph to the point where it is obvious how to match the vertices to each other, and it is hard to find counterexamples for these algorithms, but that is very difficult from having a clear proof of correctness that works for all graphs.


Is Norbert Blum's 2017 proof that $P \ne NP$ correct? Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct?

Also on topic: where else (on the internet) is its correctness being discussed?

Note: the focus of this question text has changed over time. See question comments for details.

As noted here before, Tardos' example clearly refutes the proof; it gives a monotone function, which agrees with CLIQUE on T0 and T1, but which lies in P. This would not be possible if the proof were correct, since the proof applies to this case too. However, can we pinpoint the mistake? Here is, from a post on the lipton's blog, what seems to be the place where the proof fails:

The single error is one subtle point in the proof of Theorem 6, namely in Step 1, on page 31 (and also 33, where the dual case is discussed) - a seemingly obvious claim that $C'_g$ contains all the corresponding clauses contained in $CNF'(g)$ etc, seems wrong.

To explain this in more detail, we need to go into the proof and approximation method of Berg and Ulfberg, which restates the Razborov's original proof of the exponential monotone complexity for CLIQUE in terms of DNF/CNF switches. This is how I see it:

To every node/gate $g$ of a logic circuit $\beta$ (containing binary OR/AND gates only), a conjunctive normal form $CNF(g)$, a disjunctive normal form $DNF(g)$, and approximators $C^k_g$ and $D^r_g$ are attached. $CNF$ and $DNF$ are simply the corresponding disjunctive and conjunctive normal forms of the gate output. $D^r_g$ and $C^k_g$ are also disjunctive and conjunctive forms, but of some other functions, "approximating" the gate output. They are however required to have bounded number of variables in each monomial for $D^r_g$ (less than a constant r) and in each clause for $C^k_g$ (less than a constant k).

There is notion of an "error" introduced with this approximation. How is this error computed? We are only interested in some set T0 of inputs on which our total function takes value 0, and T1 of inputs on which our total function takes value 1 (a "promise") . Now at each gate, we look only at those inputs from T0 and T1, which are correctly computed (by both $DNF(g)$ and $CNF(g)$, which represent the same function - output of gate $g$ in $\beta$) at gate output, and look how many mistakes/errors are for $C^k_g$ and $D^r_g$, compared to that. If the gate is a conjunction, then the gate output might compute more inputs from T0 correctly (but the correctly computed inputs from T1 are possibly decreased). For $C^k_g$, which is defined as a simple conjunction, there are no new errors however on all of these inputs. Now, $D^r_g$ is defined as a CNF/DNF switch of $C^k_g$, so there might be a number of new errors on T0, coming from this switch. On T1 also, there are no new errors on $C^k_g$ - each error has to be present on either of gate inputs, and similarly on $D^r_g$, switch does not introduce new errors on T1. The analysis for OR gate is dual.

So the number of errors for the final approximators is bounded by number of gates in $\beta$, times the maximal possible number of errors introduced by a CNF/DNF switch (for T0), or by a DNF/CNF switch (for T1). But the total number of errors has to be "large" in at least one case (T0 or T1), since this is a property of positive conjunctive normal forms with clauses bounded by $k$, which was the key insight of Razborov's original proof (Lemma 5 in the Blum's paper).

So what did Blum do in order to deal with negations (which are pushed to the level of inputs, so the circuit $\beta$ is still containing only binary OR/AND gates)?

His idea is to preform CNF/DNF and DNF/CNF switches restrictively, only when all variables are positive. Then the switches would work EXACTLY like in the case of Berg and Ulfberg, introducing the same amount of errors. It turns out this is the only case which needs to be considered.

So, he follows along the lines of Berg and Ulfberg, with a few distinctions. Instead of attaching $CNF(g)$, $DNF(g)$, $C^k_g$ and $D^r_g$ to each gate $g$ of circuit $\beta$, he attaches his modifications, $CNF'(g)$, $DNF'(g)$, ${C'}^k_g$ and ${D'}^r_g$, i.e. the "reduced" disjunctive and conjunctive normal forms, which he defined to differ from $CNF(g)$ and $DNF(g)$ by "absorption rule", removing negated variables from all mixed monomials/clauses (he also uses for this purpose operation denoted by R, removing some monomials/clauses entirely; as we discussed before, his somewhat informal definition of R is not really the problem, R can be made precise so it is applied at each gate but what is removed depends not only on previous two inputs but on the whole of the circuit leading up to that gate), and their approximators ${C'}^r_g$ and ${D'}^r_g$, that he also introduced.

He concludes, in Theorem 5, that for a monotone function, reduced $CNF'$ and $DNF'$ will really compute 1 and 0 on sets T1 and T0, at root node $g_0$ (whose output is the output of the whole function in $\beta$). This theorem is, I believe, correct.

Now comes the counting of errors. I believe the errors at each node are meant to be computed by comparing reduced $CNF'(g)$ and $DNF'(g)$ (which are now possibly two different functions), to ${C'}^r_g$ and ${D'}^k_g$ as he defined them. The definitions of approximators parrot definitions of $CNF'$ and $DNF'$ (Step 1) when mixing variables with negated ones, but when he deals with positive variables, he uses the switch like in the case of Berg and Ulfberg (Step 2). And indeed, in Step 2 he will introduce the same number of possible errors like before (it is the same switch, and all the involved variables are positive).

But the proof is wrong in Step 1. I think Blum is confusing $\gamma_1$, $\gamma_2$, which really come, as he defined them, from previous approximators (for gates $h_1$, $h_2$), with positive parts of $CNF'_\beta(h_1)$ and $CNF'_\beta(h_2)$. There is a difference, and hence, the statement "$C_g'$ contains still all clauses contained in $CNF'_\beta(g)$ before the approximation of the gate g which use a clause in $\gamma_1'$ or $\gamma_2'$" seems to be wrong in general.

Blum uses Razborov´s method of approximation to conclude that a function in $NP-c$ can´t be computed in $P$.

The goal of Razborov´s method of approximation is to show that $C$ cannot compute $f$, where $f$ is a boolean function and $C$ any circuit of $m$ gates.

A boolean function has an only one truth table but not a single algebraic expression, neither a problem has only one boolean function that solves it.

Some (may be all) functions are isomorphics (problems aren´t).

To conclude that $NP=P$ by Razborov´s method of aproximation, it requieres to proof that a circuit with $m$ gates (such as $m$ is polinomic respect de entries of $f$) can´t compute a $f$ function with no isomorphims, or else that $f$ is it´s minimal isomorphism.


Application of graph theory in computer science I am a CS student. We did graph theory in one course. I found it interesting.

What are the real applications of graph theory in the computer science field?

For example, I found that some concepts in graph theory can be used to design networks. What are other similar applications?

This is in no way a definitive answer, and I do not intend it as such.

Many problems of interest to computer scientists can be phrased as graph problems, and as a result graph theory shows up quite a lot in complexity theory. The computational effort required to determine where two graphs are isomorphic, for example, is currently a topic of much interest in complexity theory (it is neither known to be NP-complete nor contained in P, BPP or BQP, but is clearly in NP). Graph non-isomorphism, on the other hand, has a very nice zero-knowledge proof (another area of study in complexity theory). Many complexity classes have graph problems which are complete for that class (under some reduction).

However it is not just complexity theory that makes use of graph theory. As you can see from some of the other answers, there is quite an array of problems for which the language of graph theory is most appropriate. There are far to many applications to provide a diffinitive list, so instead I will leave you with an example of how graph theory plays a fundamental role in my own area of research.

Measurement-based quantum computation is a model of computation which does not have a counterpart in the classical world. In this model, the computation is driven by making measurements on a special class of quantum states. These states are known as graph states, because each state can be uniquely identified with an undirected graph with a number of vertices equal to the number of qubits in the graph state. This link with graph theory is more than coincidental, however. We know that an important class of measurements (Pauli-basis measurements in case you are interested) map the underlying graph state to a new graph state on one less qubit, and the rules by which this occurs are well understood. Further, properties of the underlying graph family (it's flow and g-flow) determined fully whether it supports universal computation. Lastly, for any graph G' which can be reached from another graph G by an arbitrary sequence of complementing the edges of the neighbourhood of a vertex can be reached by single-qubit operations alone, and so are equally powerful as a resource for computation. This is interesting because the number of edges, maximum of the vertex degrees, etc. can change drastically.

I once applied graph theory in a ladder diagram editor and compiler.


Is there a reduction to "door and pressure plate" games that doesn't explode solution length? This paper gives a proof that in a game with doors and pressure plates, it is PSPACE-hard to determine whether or not the (player's) avatar can reach a given location. This is proven by a reduction from TQBF, and the length of the resulting solutions depends exponentially on the number of universal quantifiers in the formula.

Is there a reduction from an NPSPACE machine to such a game for which the length of the game's solutions are polynomially related to the length of the machine's accepting paths?

Perhaps you can easily simulate a LBA; the idea is the following:

for every cell of the LBA tape add a cell gadget $G_i$ that can be entered only from the bottom and leaved only from the top;
the gadget has an entrance door $C_i$ which simulates the head position (only one $C_i$ is opened at every step);
then there are two bit doors $Z_i$ and $O_i$; $Z_i$ is opened if the cell contains a  zero, $O_i$ is opened if there cell contains a one;
both bit doors lead to a similar control structure which is made by several one-way corridors; a corridor corresponds to a state of the LBA, and the door $q_i$ of the $i$-th corridor is opened if and only if the current state of the LBA is $q_i$;
according to the (possibly non-deterministic) transition table of the LBA, a traversal of the (opened) corridor changes the current state of the LBA and the configuration of the bit-doors, closes door $C_i$ and opens $C_{i+1}$ or $C_{i-1}$.

A cell gadget is sketched in the figure below.

Non-deterministic choices can be realized splitting the corridors  in the control structures into two or more sub-corridors as shown in the figure below.

Note: if a plate can only open/close a single door, then you can add an auxiliary structure with (long) one way corridors that (de)activates the distinct state doors of each cell.

this type of research of relating video games to computational complexity is quite intriguing but it is also quite new, generally less than a decade old. I will argue here there is subtlety that is sometimes being missed in the current analyses [have not seen/noticed this pointed out in the cited paper or other papers so far] and that impedes answering the stated question definitely.

to prove a relation to a computational system, one must be able to map the computational system onto the game and vice versa. for example in the above cited paper by Viglietta there is a concept that pressure plates and doors (ie the pressure plates control doors) can be "like" QBFs. this analogy is certainly viable as they have mapped it out. one can use a QBF to solve a game with pressure plates and doors.

however, here is the subtlety. in a given game, the layouts of the game are basically fixed. in video game design the concept of different layouts is called "layout design" and is not a "given" of all games. for example in the groundbreaking game Doom, the level design tools were open-sourced ie made available to players to use. in other words arbitrary level design can be regarded as part of the game. but in other games considered in papers, the video games as originally built have fixed levels. the papers are sometimes not explicitly taking this into account.

therefore there is a strong argument to be made that in most games without level design, or random layouts, levels are fixed, and this has a big impact on the actual complexity of solving the "game". ie, what exactly is the "game"? does it include random layouts, and/or level design possibility? is level design part of the computational mapping? these issues are glossed over somewhat in current papers.

taken to the opposite extreme of the papers, one could argue that all real video game implementations are solvable by FSMs because they have finite memory!

for there to be real computational mappings, basically one must generalize the game to involve

levels with arbitrary size! so that this can be mapped to TMs with arbitrary/unlimited size "input" tapes.
level design that allows creation of these levels.

a slightly similar mapping issue arises in CA/Cellular Automata research where there are ideas about using infinite periodic patterns on the CAs as "starting patterns" to prove TM equivalence/completeness.

so in general your question is not strictly defined until you clarify better (ie more formally/mathematically define) what you mean by "in a game with doors and pressure plates" and in a way that even the paper does not apparently strictly define, esp wrt to ideas about level design, unlimited size levels, etcetera. but notice that the "games" defined with these features then have been abstracted away from the actual/real video games in a very significant way.

so in short I think this is interesting/worthwhile research, even though starting out as somewhat informal, and deserves further advancement, but to some degree its formalization must be made more strict esp in basic definitions if it is to advance further. it must make a more strict/formal/transparent distinction between the implementations and the abstractions.


Locating a set of 5 geometrically constrained points within a cloud of points What is the most efficient way to find a set of 5 geometrically constrained, non-collinear points within a 3D point cloud of, for example, 100 points?

All points are expressed with respect to a single world coordinate system.

Upper bound:

Make three sorted lists of point pointers, one for each dimension O(nlogn)

Pick a point in your reference template to be the "origin" and make 4 vectors to the other points O(1)

For each vector

Scan the list of all points to see if a sister point exists at this vector, if not throw it out as not an origin candidate.  O(n)

If you allow rotations you are probably going to have to throw it in a quadtree and do some range queries; but after the first few are matched to the template it will be oriented allowing you to go back to vector lookups.


Real world applications of quantum computing (except for security) Let's assume that we have built an universal quantum computer.

Except for security-related issues (cryptography, privacy, ...) which current real world problems can benefit from using it?

I am interested in both:

problems currently unsolvable for a practical entry,
problems which currently are being resolved, but a significant speedup would greatly improve their usability.

Efficiently simulating quantum mechanics.

think you've raised an excellent question at the frontiers of QM research (partially indicated by your lack of answers so far), but it hasnt been entirely formally defined or captured as a problem. the question is along the lines of "what exactly can QM algorithms compute efficiently anyway?" and a complete answer is not known & being actively pursued. some of this is related to the (open questions on) complexity of QM-related classes.

this would be the case that there is a somewhat formal question defined. if the QM classes can be shown to be equivalent to "significantly powerful" non-QM classes, then there's your answer. the general theme of this type of result would be a "not-so-hard-in-QM" class is equivalent to a "hard-in-non-QM" class. there are various open complexity class separations of this type (maybe someone else can suggest them in more detail).

something strange about current QM knowledge on quantum algorithms
is that theres a kind of weird grab bag of algorithms that are known to work in QM but theres seemingly not a lot of coherence/cohesion to them. they seem odd and disconnected in some ways. theres no apparent "rule of thumb" for "problems that are computable in QM are generally in this form" despite a reasonable expectation that one could be there.

e.g. contrast this to the theory of NP completeness which is much more cohesive in comparison. it seems like maybe if the QM theory is better developed it would obtain this greater sense of cohesion reminiscent of NP completeness theory.

a stronger idea might be that eventually when the QM complexity theory is fleshed out better, NP completeness will fit "neatly" into it somehow.

to me the most general QM speedup or widely applicable strategy Ive seen seems to be Grovers algorithm because so much practical software is related to db queries. and in some ways increasingly "unstructured" ones:

  Grover's algorithm searches an unstructured database (or an unordered list) with N entries, for a marked entry, using only $O(\sqrt{N})$ queries instead of the $Ω(N)$ queries required classically.


Beating naive dynamic programming: examples similar to integer partitions? Let $p(n)$ denote the number of partitions of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming algorithm to find $p(n)$ is to construct a square table $A$ where
$$A_{i,j} = \text{partitions of $i$ where each part is $\leq j$}$$
and recursively fill it using the rules
$$A_{i,j} = A_{i,j-1} \text{ if }j>i$$
and
$$A_{i,j} = A_{i,j-1} + A_{i-j,j}\text{ otherwise}$$
with the appropriate conventions for the corner cases. Then $p(n)=A_{n,n}$. This takes $O(n^2)$ operations on integers (let's say we're looking for $p(n)$ modulo some big number, so the size of the numbers is $O(1)$). We can optimize the memory down to $O(n)$ by noticing that we only need the previous column to find the next one.

However, the pentagonal number theorem due to Euler says that
$$p(n) = \sum_{k\in\mathbb{Z}:g_k\leq n}(-1)^{k+1}p(n-g_k)$$
where $g_k = k(3k-1)/2$ are the pentagonal numbers. This allows us to recursively build a one-dimensional list of the $p(i)$, using only $O(n\sqrt{n})$ operations, since the above sum contains $O(\sqrt{n})$ terms.

My question: I was wondering if there are other examples of natural problems for which there is such a surprising speed-up over the standard dynamic programming algorithm, or if this is more of an isolated case complexity-wise.

One nice example is the Hamiltonian Path problem is easily solvable in $O(2^n(n+m))$ time (Bellman, 1962) by dynamic programming over vertex subsets. In 2010 Björklund gave an algorithm running in time $O(1.657^n)$ using determinants and polynomial identity testing in a field of characteristic $2$.

Another example is that of “connectivity problems”, such as Hamiltonian Path, Steiner Tree, or Feedback Vertex Set on graphs of treewidth $k$. The naive dynamic programming algorithms for these problems run in time $2^{O(k \log k)}n^{O(1)}$, and at a glance it really looks like that is what the ``correct’’ running time for these problems should be. However, in a wonderful paper, Cygan et al. showed that these problems all allow algorithms with running time $2^{O(k)}n^{O(1)}$, again cleverly using polynomial identity testing in a field of characteristic 2.

The bounded knapsack problem is: you are given n types of items, you have ui items of i-th type, and each item of i-th type weighs wi and costs ci. What is the maximal cost you can get by picking some items weighing at most W in total?

The link provides the solution in O(W*n).

http://petr-mitrichev.blogspot.com/2011/07/integral-bounded-knapsack-problem.html


Polynomial-time algorithms with huge exponent/constant Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, where the proven upper bound on the running time is in such a way)?

Here are two screenshots from An Energy-Driven Approach to Linkage Unfolding by Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben,  James F. O’Brien, SOCG 2004:

surprisingly one of the most obvious answers not posted yet. finding a clique of size $c$ (edges or vertices) apparently takes $O(n^c)$ time by the naive/brute force algorithm that enumerates all possibilities. or more accurately proportional to $n \choose c$ steps. (strangely enough this basic factoid seems to be rarely pointed out in the literature.) however a strict proof of that would imply $\mathsf{P \neq NP}$. so this question is related to the famous open conjecture, virtually equivalent to it. other NP type problems can be parameterized in this way.


Circuit Complexity Charaterization for DLogTime and NLogTime $\mathsf{DLogTime}$ and $\mathsf{NLogTime}$ are two of the smallest complexity classes we have. (Note that logarithmic time hierarchy $\mathsf{LH}$ is equal to $\mathsf{AC}^0$ and these are the first two level of $\mathsf{LH}$).

After reading this question, I become interested to see if the separation between these two classes is known, and in fact it is easy to separate them since $OR(x_1,...,x_n) \in \mathsf{NLogTime}-\mathsf{DLogTime}$ (thanks to Robin Kothari. See also known). Now I am interested to know their corresponding circuit complexity characterization. I have searched a little bit and have asked a few people but was not able to find the answer.

  Do we have nice circuit complexity characterizations for complexity classes $\mathsf{DLogTime}$ and $\mathsf{NLogTime}$?

Note: $\mathsf{DLogTime}$ shows up a lot in defining uniformity for small complexity classes. Note that the small time bound does not allow these machines to read the whole input, they can only read $\lg n$ bits from the input, and the classes are defined using machines that can write the address of a bit and then read that bit directly (i.e. don't need to go over all previous bits to reach there).

I think it is far more interesting that the circuit complexity classes used by CS complexity theory make different predictions and use different metrics than those in the VLSI community.  From The VLSI complexity of Boolean functions:

  It is well-known that all Boolean functions of $n$ variables can be computed by a logic circuit with $O(2^n/n)$ gates (Lupanov's theorem) and that there exist Boolean functions of n variables which require logic circuits of this size (Shannon's theorem). We present corresponding results for Boolean functions computed by VLSI circuits, using Thompson's model of a VLSI chip. We prove that all Boolean functions of $n$ variables can be computed by a VLSI circuit of $O(2^n)$ area and period 1, and we prove that there exist Boolean functions of $n$ variables for which every (convex) VLSI chip must have $\Omega(2^n)$ area.

Interestingly, VLSI circuit complexity has a tendency to treat depth as "irrelevant" as there is one and only one "depth" that matters: the critical path.  For most practical purposes, an arbitrarily complex circuit can be treated as $O(1)$ with a latency of $n$.

In fact, I'm not even sure that the concept of $DLogTime$ / $NLogTime$ directly translates in to VLSI circuit complexity.  Even Shannons $2^n/n$ result does not readily translate: Shannons results is valid only for a boolean basis consisting of arity $\le2$ {AND, OR, NOT}.  This is not the only basis, and the number of "gates" needed drops dramatically as you allow more and more gate types.  The following are $area^2$ from a commercial VLSI standard cell library normalized to the size of a 2 input NAND gate:

        2    3    4    <- Arity
and    1.14 1.28 1.41
nand   1.00 1.14 1.28
or     1.14 1.41 1.41
nor    1.00 1.14 1.41
xor    1.62 2.44
xnor   1.62 2.44

buf    1.14
inv    0.80

aoi22  1.28
aoi222 1.62
aoi33  1.62
oai22  1.41
oai222 1.72
oai33  1.62

addf   2.64

Specifically, note the aoi / oai gates which are And Or Invert / Or And Invert consisting of arity sized first function feeding the second function, where the number of first function gates is equal to the number of times arity appears.  For example, aoi22 represents "Two 2 input AND gates feeding a NOR gate".

My point is: Taken separately, a oai222 function can be built using three 2 input OR gates and a 3 input NAND gate, for a total area of ~4.56, not including any area used for interconnect.  Yet this primitive can be realized in an area of just 1.72, which means a discrete manifestation of the same boolean function consumes 2.65 times more area.

Also note that the area for an $n$ input {AND, NAND, OR, NOR, XOR, XNOR} gate, where $n\ge2$, is much less than the area that it would take to build the same function using discrete 2 input gates.  Also note that while the area given for {XOR, XNOR} for this process is "large" relative to the other gates, there are other ways to build the same $n$ input gates using less area.

The propagation properties for the more complex primitives is also significantly better than what would be achieved using discrete gates.

Why is this important?  Because for me, at least, I've spent a simply enormous amount of time sifting through results from complexity theory that are built on a set of assumptions that has the effect of either rendering the result useless or wrong once the assumption is violated.  The following is from Steven Cooks $\mathcal{P}$ vs $\mathcal{NP}$:

  Thus to prove $\mathcal{P} \ne \mathcal{NP}$ it suffices to prove a super-polynomial lower bound on the size of any family of Boolean circuits solving some specific $\mathcal{NP}$-complete problem, such as 3-SAT. Back in 1949 Shannon proved that for almost all Boolean functions $f : \{0,1\}^n \to \{0,1\}$, any Boolean circuit computing $f$ requires at least $2^n/n$ gates. Unfortunately, his counting argument gives no clue as to how to prove lower bounds for problems in $\mathcal{NP}$.

I find Cooks reasoning curious.  Shannons result is valid for all $f : \{0,1\}^n \to \{0,1\}$, therefore if a $\mathcal{NP}$ problem can be described in $\{0,1\}^n$ bits, there must be a {AND, OR, NOT} basis circuit that can decide if it is satisfiable in ~$2^n/n$ gates (the actual paper gives a larger upper, but finite, bound for every possible function).  What this tells us is that anything that uses more than $n$ gates, where $n$ is the upper bound for the size of the $\mathcal{NP}$ problem, is using more gates than is required.  Using a larger, but complete, boolean basis only reduces the number of gates required.  Using a different circuit complexity model, i.e. VLSI, gives even "better" result bounds.  Curious.  But we know for a fact that any solution to a $\mathcal{NP}$ problem that uses more than ~$2^n/n$ "gates" (where gates is used loosely for steps / operations) is doing so in a sub-optimal fashion... and there's an infinite number of ways to find a solution in a sub-optimal fashion.

On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication shows that predicting circuit complexity using a OBDD model over-estimates the actual circuit complexity:

  Lower-bound results on Boolean-function complexity under two different models are discussed. The first is an abstraction of tradeoffs between chip area and speed in very-large-scale-integrated (VLSI) circuits. The second is the ordered binary decision diagram (OBDD) representation used as a data structure for symbolically representing and manipulating Boolean functions. The lower bounds demonstrate the fundamental limitations of VLSI as an implementation medium, and that of the OBDD as a data structure. It is shown that the same technique used to prove that any VLSI implementation of a single output Boolean function has area-time complexity $AT^2 = \Omega (n^2)$ also proves that any OBDD representation of the function has $\Omega(c^n)$ vertices for some $c<1$ but that the converse is not true. There are functions for which any OBDD representation is of exponential size, but there is a VLSI implementation of complexity $AT^2 = O(n^{1+c})$.

  An integer multiplier for word size $n$ with outputs numbered 0 (least significant) through $2n-1$ (most significant) is described. For the Boolean function representing either output $i-1$ or output $2n-i-1$, where $1\le i\le n$, the following lower bounds are proved: any VLSI implementation must have $AT^2 = \Omega(i^2)$ and any OBDD representation must have $\Omega(1.09^i)$ vertices.


Is "normalized distance" (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing? In "The Similarity Metric" (Li, Vitanyi, et. al) they define a normalized distance (or similarity distance) as a function $\Omega \times \Omega \to [0,1]$ which is both symmetric and satisfies the density requirement for every $x \in \Omega$ and every constant $c \in [0,1]$:

$\displaystyle |\left \{ y : d(x,y) \leq c \right \}| < 2^{cK(x)+1}$

They give a somewhat convoluted example of a normalized version of the Hamming distance which satisfies this definition, and they prove that their normalized information distance satisfies this definition as well.

It is not at all clear to me that this definition represents a wide variety of "distance" measurements. Their conclusion is that because the normalized information distance is universal in this class of metrics, it is philosophically universal in all metrics we care about. But it's not even obvious to me that Euclidean distance (restricted to $\left \{0,1\right \}^n$) can be modified to satisfy this definition. That's not even close to mentioning distance measures for, say, language sentiment or other distances used in applications.

It would be great if we could say, for instance, that every computable metric has a normalized version which satisfies this definition. Is this known? If not, what is known?

The distance should be upper semicomputable. For instance the Hamming distance or Euclidean distance as such is not. One has to turn them into a version that satisfies the requirement above. Read the paper closer.


Formalizing a notion of machine Intelligence Turing test of Artificial intelligence relies on interaction between two parties with the goal that one party convinces the other party that it has the same computational abilities.

I'm trying to formalize a new notion of machine Intelligence: the ability of Turing machines (algorithms) to recognize their programmer and that they were not generated randomly.
This requires defining metrics to be used by Turing machines to measure the creative abilities of the programmer. We may allow interaction between the algorithm and the programmer.

  How can we formalize such notion of AI? Has any similar idea been investigated before in TCS?

EDIT1: programmer here is a program that is able to generate other algorithms runnable on some computing device.

One motivation is whether intelligence of an algorithm is dependent on programmer's intelligence.

EDIT2: I'd like to formalize a notion for the intelligence and creativity of programs. Not all programs created equal. My question is an attempt to model and formalize aspects of intelligence that are not captured by current definitions of AI. For instance, Does an evolutionary algorithm possess any intelligence? If yes, What is the source of this intelligence?

EDIT3: My goal is to remove the subjectivity from Turing test. If the programmer is able to convince a Turing machine that it was the product of creativity of the programmer then the Turing machine is intelligent. Furthermore, the programmer is far more intelligent than the code he created. So, the challenge is how to formally convince the Turing machine that the programmer has superior computational abilities. In addition, the programmer must convince the Turing machine that those superior computational abilities are required and critical to the creation of the Turing machine code.

Let me give a partial answer from a learning theory perspective.  As your question isn't well specified, this answer won't be either.  In my answer, I'm assuming your question was inspired by your blog post, linked from your profile.

Say that you are thinking about programs that are just functions (so they have to halt, etc.).  You can ask whether certain classes of such functions can appear randomly by, perhaps, looking at the probability a random program (from some distribution that you think is likely) lands in that class or not, with the hope that probability is polynomially large.  I haven't really thought this argument through.

You can also ask whether such a class is efficiently evolvable according to Valiant's model of evolution (also in @Artem's pointer in comments): luckily what is efficiently evolvable is known to be the class learnable by correlational statistical queries; taking "crossover" into account, you get parallel correlational statistical queries. One thing to note is that just because evolvability is characterized, it is still a separate and sometimes difficult task to determine whether a particular class is evolvable (learnable with CSQs) or not.

If you find a class of "programs" that is neither randomly occurring nor evolvable, perhaps you can conclue it has a "creator/programmer," though that conclusion may still take a leap of faith.

I think quantifying computer intelligence by something so unquantifiable as the creativity of its author might prove unfruitful. It is an interesting notion, however. I would perhaps look at how large or complex the language is that the TM accepts. This is much easier to quantify, and it has been shown that there is a 1-1 correspondence to a TM and its language. It follows that if the TM's language is more complex, the machine is more "intelligent".


Collaborative tools for dummies/professors Suppose that coauthors from two or more different institutions are writing a paper in latex, and would like to do better than repeatedly emailing drafts back and forth.

They realize they can open for free a dropbox account, share the password, and synch the version of the paper on their computer with the one on dropbox. If two people are simultaneously editing the same section, however, they'll overwrite each other changes.

They have also heard that version-control systems like SVN and Git have tools to merge concurrent changes, which work reasonably well. The documentation of these products, however, is rather hard to read, and it is more focused on how to undo changes and how to manage different "branches" rather than on the basic needs of coauthors writing a paper.

Is there a simple step-by-step exposition on how to use a version-control system in this setup:

 central repository
 local copies
 "smart" merge
 no branches

?

Of the standard version-control systems, which one is the easiest to use? (We are talking theoretical computer science professors here.)

Are there even simpler tools that  only do synch with smart merge, without version control?

Conversely, do people who use version-control systems to even write a single-authored paper really feel that the unlimited-undo capability is worth the extra complexity?

First off: If your are interested in real-time collaborative editing, try something like gobby. It lets you literally edit a document at the same time.

As for revision systems, I am only familiar with SVN. This is what you do, after installing subversion, of course:

Get someone to set you up a repository and give you URL, username and password
Go to where you want to have your lokal copy
In a shell (command line?), type: svn co url://to.your/repository (check-out). Now a new folder with the repository's contents appears.

That's all. Now the most basic commands:

Whenever you add a new file foo, enter: svn add foo
Whenever you want to remove a file, enter: svn rm foo
Whenever you have made changes, enter: svn ci (check-in)
Whenever you want to get the newest stuff, enter: svn up (update)

There are also commands for moving, copying, branching, resolving conflicts,  ... but as long as you do not try funny stuff, you are fine with the above. If anything breaks or seems to, backup your edits, delete the whole folder and checkout the whole thing anew. That's for svn like rebooting for Windows.

Addendum: I see you seem to be concerned about "smart merges". I assume that you refer to have to different versions of a file merged, with the assumption that two people added things in disjoint parts of the paper. As far as I know, svn would treat that as a conflict, and probably rightly so. I don't think that there is a general procedure that ensures you get what you want after two people manipulated the same source. There are graphical svn clients that visualise such conflicts and help you resolving them; they are pretty much diff-viewers were you can choose which version to keep for every conflicting line). It will require work, though.

SVN is the tool developed for this purpose.  I would put in the effort to learn it.   It is not more complicated than learning to use say the algorithm2e Latex package or one of the pdf slide creator Latex packages.

Having said that, I use CVS instead of SVN.  There is better support from the CS admins at our institution (the SVN server is more user managed).  Plus, I appreciate that the underlying version files are still there and editable if something goes very-very wrong.

There are 2 drawbacks when compared to SVN.  File renames are not as nice, but I can live with that (pick a good name first time).  The second problem is that one needs a local CS account to access the repository.  Therefore from another institution access is only possible if an account is created first.  Of course I do not expect this to be a real problem anywhere; a local department member can probably sponsor that account.

The local access restriction is due to the fact that the admins do not want to support a pserver.  (Harder to secure etc.)


Smallest set that intersects some given sets Let $S_1,S_2,\ldots,S_n$ be sets that may have elements in common.  I'm looking for a smallest set $X$ such that $\forall i,\,X\cap S_i \ne \emptyset$.

Does this problem have a name?  Or does it reduce to some known problem?

In my context $S_1,\ldots,S_n$ describe the elementary cycles of a strongly connected component, and I'm looking for a smallest set of vertices $X$ that intersects all cycles.

Your first problem is the hypergraph transversal problem (aka the HITTING SET problem). The second problem is the FEEDBACK VERTEX SET problem. Both the problems are NP-complete.

If we consider S1,S2...Sn as a different sequences and if we need the longest subsequence which is common in this sequences then this type of problem is called as "Longest Common Subsequence (LCS)". We can alter the condition to make it as a smallest common subsequence which will find a single element from the set as a smallest subsequence..

Please see dynamic programing examples you will get the details...


What kind of theoretical object corresponds to a C++ concept? I am lacking a background in theoretical computer science but I would have liked to understand to what kind of theoretical objects C++ concepts corresponds to. Basically, C++ concepts allow to define a set of types that satisfy a list of constraints. So, from a theoretical standpoint, what C++ concepts correspond, or roughly correspond (and in that case what are the differences), to?

From a programming language theory perspective, as opposed to the computability perspective other answers and comments have offered, C++ templates combined with concepts correspond to bounded polymorphism or constrained genericity. Concepts themselves correspond to the constraints or bounds placed on a type.

A template is type-level function, parameterised by type that are constrained by a concept to implement a particular interface. When the template is applied to a type satisfying that concept, a new type results.

Templates+concepts are analogous to generics in Java, Scala or Eiffel. They differ from templates in earlier C++ because they allow constraints on the type parameters to be specified and checked, whereas C++ templates did not allow that. The benefit is better static checking that the program after applying the template will be well typed.

A good reference is Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press, Chapter 26: Bounded quantification.

C++ concepts map to recursively enumerable languages.  Since the C++ type system is Turing complete, any property of types that can be interrogated during template instantition (size, parameters, etc.) can be run through an arbitrary program simulated in the type system.


What's the most efficient algorithm for Divisibility? What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask for is not (necessarily) an algorithm for Remainder Calculation. I just want to know whether $a$ divides $b$ or not. Being more specific, my question is whether exists or not some recent algorithm for Divisibility with time complexity better than $O(m\log m\log\log m)$, where $m$ is the number of bits of $\max\{a,b\}$. Further, is $\Omega(m\log m\log\log m)$ the lower bound of this problem?

Thanks and regards, and sorry if this is such a naive question.

Fleshing out my comments into an answer: since divisibility is (trivially) reducible to division, and since division is (nontrivially) reducible to multiplication via approaches like Newton's method, then your problem should have the same time complexity as integer multiplication.  AFAIK, there are no known lower bounds for multiplication better than the trivial linear one, so the same should hold true of your problem - and in particular, since multiplication is known to have (essentially) $O(n\log n\log^* n)$ algorithms, your hopes for a $n\log n\log\log n$ lower bound are almost certainly in vain.

The reason that division reduces precisely in complexity to multiplication — as I understand it — is that Newton's method will do a sequence of multiplications of different escalating sizes; this means that if there's an algorithm for multiplication with complexity $\Theta(f(n))$ then the complexity of a division algorithm using this multiplication algorithm as an intermediate step will be along the lines of $\Theta\left(\sum_{k=0}^{\lg n} f(\frac{n}{2^k})\right)$ — and for all of the complexity classes under discussion this is just $\Theta(f(n))$.

I think there are Vedic type of hacks for some numbers ending in 3,7 etc. Or base 2^n divisors...

But generally speaking, the fastest division algorithm seems to be the norm.

The best one I know of without looking is Algorithm D of Knuth's Seminumerical methods... Never checked its correctness though. It runs in more or less O(mn-n^2) where m and n are the dividend and divisor... without factoring multiplication complexity...

A lower bound however could be surpringly low as your question is only concerned with the decision problem.


Communication complexity of finding common element of two subsets Suppose that Alice receives a subset $S \subseteq \{1,\dots,n\}$ and Bob receives $T \subseteq \{1,\dots,n\}$.  It is promised that $\lvert S \cap T \rvert = 1$.  What is the randomized communication complexity of determining the common element $S \cap T$?

My interest in this is as follows.  The zero-communication cost of this problem is $\log n$ since Alice and Bob can just guess $S \cap T$ using public coins and abort if they guess wrong.  However, I can't think of an $O(\log n)$ cost communication protocol.  Since it is not known whether zero-communication cost is much less than randomized communication cost, I am thinking that I am missing something obvious here.

Zero-communication cost is defined as follows.  After Alice and Bob receive their inputs, they must not communicate at all.  However, they share public coins, and they are allowed to answer with "abort".  If neither party aborts, they must provide the correct answer with $2/3$ probability.  The zero-communication cost is the negative log of the probability of not aborting.  In arxiv:1204.1505 it is shown (among other things) that nearly all known lower bounds on communication complexity are in fact lower bounds for zero-communication.

Update: @Shitikanth showed that the communication complexity is $\Omega(n)$.  So, apparently this gives a gap between communication cost and zero-communication cost.  But arxiv:1204.1505 seems to give the impression that no such gap is known.  What am I missing?

(Reduction from set disjointness)

Suppose Alice and Bob are given sets $S, T \subseteq [n]$ with the guarantee
that $|S\cap T| \leq 1$. Alice and Bob run the protocol for finding the common
element of $S$ and $T$ assuming that their sets have a non-trivial intersection
to decide a common element $X$. Now, they can communicate with each other to
verify that $X$ is in fact common to both $S$ and $T$ with $O(\log n)$ bits.

Therefore, any protocol for finding the common element of $S$ and $T$ must take $\Omega(n)$ bits of communication.

Fastest protocol I can think of is alternate exchanging a random adjacent pair of elements, throwing away stuff that gets skipped over.

Alice[1,10,26,49,50] Bob[2,3,25,49,51]

Alice adjacent pair is [10,26] so Bob throws away 25

Alice[1,49,50] Bob[2,3,49,51]

Bob adjacent pair is [3,49] match on 49 so halt


Oracle results on P vs BPP Let $A$ be any EXP complete problem. Then, $P^A = NP^A$.

Let $B$ be some oracle that takes into accounts the queries that $M$ (a TM in P) will make, and we can get $P^B \neq NP^B$.

Question: Do we have similar oracle results for P vs BPP?

I had a vague recollection that I knew an excellent reference for such oracle separations. I finally found it.

A great reference for oracle separations (for classes between P and PSPACE) is the following paper:

  Vereshchagin, N K (1994), "RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS", Russian Academy of Sciences. Izvestiya Mathematics 42 (2): 261

The paper shows (or gives a citation for) an oracle separation between almost every pair of classes that you might care about between P and PSPACE (e.g., it has classes like P, RP, BPP, UP, FewP, NP, MA, AM, other levels of PH, PH, IP, PSPACE, etc.).

For example, Theorem 8 shows an oracle problem in coRP that is not in NP. Since (relative to all oracles) coRP is in BPP and NP contains P, we get an oracle problem in BPP that is not in P.

As I mentioned in my comment, showing an oracle for which $\text{P}^A = \text{BPP}^A$ is easy. Let A be a EXP-complete language or a PSPACE-complete language.

Bennett & Gill give oracles for both cases: http://epubs.siam.org/doi/abs/10.1137/0210008


Are there analogous works to PPSZ algorithm for #P? The PPSZ algorithm tells us that we can do SAT-solving for
$k-$CNF in time at-most $2^{1-(1-o(1))\frac{\pi^2}{6k}}$.
My question is that do we know such results for counting problems in class #P too ? For example, for #SAT do we know any algorithm that provably runs better than $O(2^n)$ ?

There are several #k-SAT algorithms in the literature which can beat $2^n$. Here is a randomized one that gets
$2^{n(1-1/O(k))}$ time (like PPSZ):
https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoMatthewsPaturi_2012_soda.pdf
There is also a deterministic algorithm with $2^{n(1-1/O(k))}$ runtime behavior. Here is a link:
http://tmc.web.engr.illinois.edu/detapsp_soda.pdf
A caveat: this second algorithm uses exponential space. I believe it is open to find a deterministic algorithm with a similar running time and polynomial space. Be sure look on Google scholar for related references too.

Recently, I have presented a randomized algorithm for #$k$-SAT which counts the exact number of satisfying assignments in $2^{o(n)}$ time (and linear space), thereby refuting #ETH and related hypotheses:
The #ETH is False, #k-SAT is in Sub-Exponential Time
The crucial insight is: count without search. The algorithm counts all satisfying assignments without even trying to search for any single one of them. Thanks to the inclusion-exclusion principle, it is possible to count satisfying assignments by totally ignoring them and by visiting a completely different search space: that of monotone (unate) sub-formulae. A further insight allows, for random instances, to prune such search space so massively that only the last $n$ clauses do matter for the running time (regardless of the density $\Delta = \frac{m}{n}$ which in general might depend on $k$ exponentially), resulting into a $2^{\Theta(\frac{\log k}{k})n}$ time deterministic algorithm. A final simple trick allows to take any generic instance and inflate (i.e. dilute) it by randomly enlonging all its clauses and arranging them so that it looks random and fools the algorithm for random instances.
The final running time for generic #$k$-SAT instances is $2^{O\left(\frac{\log \log \log n}{\log \log n}n\right)}$.


Are runtime bounds in P decidable? (answer: no) The question asked is whether the following question is decidable:

  Problem  Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect to input length $n$ ?

A narrow answer of "yes", "no", or "open" is acceptable (with references, proof sketch, or a review of present knowledge), but broader answers too are very welcome.

Answer

Emanuele Viola has posted a proof  that the question is undecidable (see below).

Background

For me, this question arose naturally in parsing Luca Tevisan's answer to the question Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?

The question relates also to a MathOverflow question: What are the most attractive Turing undecidable problems in mathematics?, in a variation in which the word "mathematics" is changed to "engineering," in recognition that runtime estimation is an ubiquitous engineering problem associated to (for example) control theory and circuit design.

Thus, the broad objective in asking this question is to gain a better appreciation/intuition regarding which practical aspects of runtime estimation in the complexity class P are feasible (that is, require computational resources in P to estimate), versus infeasible (that is, require computational resources in EXP to estimate), versus formally undecidable.

--- edit (post-answer) ---

I have added Viola's theorem to MathOverflow's  community wiki "Attractive Turing-undecidable problems".  It is that wiki's first contribution associated to the complexity class P; this attests to the novelty, naturality, and broad scope of Viola's theorem (and IMHO its beauty too).

--- edit (post-answer) ---

Juris Hartmanis' monograph Feasible computations and provable complexity properties (1978) covers much of the same material as Emanuele Viola's proof.

The problem is undecidable. Specifically, you can reduce the halting problem to it as follows. Given an instance $(M,x)$ of the halting problem, construct a new machine $M'$ that works as follows: on inputs of length $n$, it simulates $M$ on $x$ for $n$ steps. If $M$ accepts, loop for $n^2$ steps and stop; otherwise loop for $n^3$ steps and stop.

If $M$ halts on $x$ it does so in $t=O(1)$ steps, so the run time of $M'$ would be $O(n^2)$. If $M$ never halts then the run time of $M'$ is at least $n^3$.

Hence you can decide if $M$ accepts $x$ by deciding if the run time of $M'$ is $O(n^2)$ or $O(n^3)$.

The solution from Viola can be generalized to any running time (beyond poly): You can reduce the halting problem to it as follows. Given an instance (M,x) of the halting problem, construct a new machine M′ that works as follows: on inputs of length n, it simulates M on x for f(n) steps or until M halts, where f(n) is any arbitrary increasing function (greater than constant) of n. (Obs.: M′ reads gradually the input, in order to avoid wasting linear time [O(n)] just to read needlessly all the input, if it is large enough and M halts.)

If M halts on x it does so in T=O(1) steps, so the run time of M′ would be O(1). If M never halts then the run time of M′ is O(n^2*f(n)).

Hence you can decide if M accepts x by deciding if the run time of M′ is O(1) or O(n^2*f(n)).

Then, the auxiliary code from Raphael can be generalized accordingly by:

Let (M,x) be any instance of the Halting Problem, that is we have to decide whether M halts on x. Construct a deterministic Turing Machine (DTM) M* that works as follows:

M*(input) = {
n := 0
Read the first symbol from the input
Loop:
n := n+1
Simulate M(x) for f(n) steps or until M(x) halts
Read the next symbol from the input
Loop until end_of_input or until M(x) has halted
}

Now we observe the following implications:

M halts on x after at most k (constant) steps => T(M*) = O(1) and

M never halts on x => T(M*) = O(n^2*f(n))

Therefore, even deciding whether the running time of an arbitrary DTM is simply greater than constant is as hard as Halting Problem. □


Graph Isomorphism Problem I am doing some literature review on Graph isomorphism problem. Most of papers which I am reading are written by E.M Luks and Laszlo Babai.
These papers uses the high level knowledge of group theory and complexity theory.
As I am new to this field many of the things are not clear to me.

Can some one suggest me a way to learn ideas and techniques which are presented in these papers so that I can come up with some other ideas.

Thank you so much

I highly recommend Paolo Codenotti's thesis for the group-theoretic aspects, and the book The Graph Isomorphism Problem: Its Structural Complexity by Johannes Köbler, Uwe Schöning, and Jacobo Torán for the complexity aspects.

http://oeis.org/A186202 is the best you can do for automorphism by brute force permutation checking.


Proving properties about a compilation from one problem into another Say I have two problems A and B.

A is the shortest path problem with positive weights

B is the shortest path problem (with potentially negative weights)

I would like to show: There is no mapping m, from B to A such that for every instance I_B of B the exact solutions for m(I_B) is the same as for I_B.

What I would like to know is where can I find proofs of this kind?
How would you approach something like this?

Let's assume that the weights are integers (for both A and B), and that m must be onto.  You could also assume that m must be a bijection (i.e., one-to-one and onto) and it would make no difference; the proposition you present is still false.

The reason is that all weighted digraphs (I'm assuming that's what you mean, not that it matters) are isomorphic to each other.

Let's prove:  There exists a mapping m : B -> A s.t. for all instances I_B of B, the solution S(m(I_B)) = S(I_B).

To show this, we will construct this mapping m.  Further, we'll show that m is a bijection.

We will divide the set of all digraphs into partitions.  Each partition will contain all graphs of a particular number of nodes N, and a particular solution structure that makes all graphs in the partition isomorphic to each other, in the sense that all solutions paths are the same.  (We index each node in an N-node graph from 1 to N, and consider two solution paths to be identical iff they contain exactly the same indexes in the exact same order and both have N nodes.)

Observe that each such partition has a countably infinite cardinality, due to the fact that there are infinitely many weight possibilities for each edge.  (Proof omitted.)

Thus, to construct m, all we must do is map every member of a partition (in B) to another member of the corresponding partition (in A).  Obviously, B contains extra graphs, but both have all partitions with the same cardinality as the set of natural numbers.

Now, we have that m is a bijection because every element in each partition of B maps to a unique element in the corresponding partition of A...and every element of every partition of B can be mapped to for each partition of A.


Difference between syntax and semantic error in programming languages When compilers generate errors for a specific programming language, there's distinction between syntax & semantic errors. E.g. ) + f 3 has ill-formed syntax, but type checking is considered as part of semantic analysis.

My intuition tells me that, by setting more constraints on the language syntax, some semantic errors can become syntax errors. And my question is if there are any intrinsic differences between syntax and semantics? Or are they just checking performed on different levels, for example syntax checking is a rather local checking while semantic checking is global? Is there anything fundamental that makes semantics checking different from syntax checking? Is it possible to embed all semantic checking within syntax? Are there any theories related to these questions?

It may also be the case that my intuition is wrong - if that's the case, please also explain to me why that is wrong.

In the strictest sense, there is no real difference between syntax errors and semantics errors, at least as far as language theory is concerned: the only salient difference is the complexity of the automaton required to recognize that language, with, e.g.

Context-free languages only requiring pushdown automata (PDA)
General recursive languages requiring full Turing machines (TM)

If every "syntactic task" merely required pushdown automata and every "semantic task" something more, then the matter would be settled, but unfortunately there are many tasks that are associated with programming language syntax that cannot be handled by PDA alone, and conversely, some semantic tasks which seem to require only weak computation power. Still, the distinction provides some intuition.

Pragmatically, compilers are designed in phases, which makes managing the task of generating executable code manageable. I particularly like this diagram from the Compcert website.

Typically, the first 1-3 phases turn what is essentially a stream of bytes or tokens into something more naturally seen as a tree structure. Everything before the tree creation will be labelled as "syntax" and everything after as "semantics".

In C, the syntactic phases are typically tokenization, macro expansion and parsing, everything after that will be semantics. Again, opinions may differ, since there is no accepted formal distinction.

I think there's a larger discussion to be had about how to distinguish syntactic notions from semantic notions in the field of formal logic, but I'm not sure I feel qualified to have it.

To simplify all that I've read about, basically:
The syntax of a programming language is a collection of rules to specify the structure or form of code whereas semantics refers to the interpretation of the code or the associated meaning of the symbols, characters or any part of a program.

True??


Factoring as a decision problem I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision problem? And is there a paper which shows that Shor's algorithm implies this decision problem is in BQP?

Here the goal is to construct a decision problem D so that (a) if you can factor you can solve the decision problem in polynomial time and (b) if you can solve the decision problem you can factor in polynomial time.   There are a number of ways to do this.  To name just two:

D:  given n and k, does n have a divisor d satisfying 1 < d <= k?
D:  given n and j, is the j'th bit of the smallest nonunit divisor of n equal to 1?

If you can solve 1, then you can identify d using binary search.  Once you have d, you can then continue with n/d until the complete factorization is achieved.  2 is similar.

If I understand correctly, factoring can be encoded as SAT decision problem and then recover the actual solution. For unknown $x,y$ and given $N$, encode to SAT the problem $ x \cdot y = N, x > 1 , y > 1$. Basically all you need is an adder circuit and few gates. Call the resulting formula $\phi$. If $\phi$ is satisfiable, then $N$ is composite. Set the first bit of $x$ to $1$ and check if $\phi'$ is satisfiable. If it is, you guessed correctly and try with the second bit. Otherwise set it to $0$ and continue with the second bit. This is linear in the numbers of bits.

(Actually in practice real SAT solvers will give you the complete
solution if it exists).


Fast computation of Frobenius norm under memory limits Given a large dense matrix $A^{n \times n}$, that does not fit to the memory (RAM). Is there any fast way to compute the exact Frobenius norm of the matrix or its accurate approximation (perhaps, via sampling with reasonable bounds provided)? What if this matrix is a subtraction of two $n \times n$ matrices: $\| A - B \|_F$, where $A$ is sparse, and B is dense?

Some of the results depend on the model under which the matrix is presented, but there's a large collection of results that use sampling or sketching techniques to estimate norms accurately. Among some of the key results are:

sketching methods based on the use of 2-stable distributions: these work even if the entries are "streamed in" in some order, and also work if you are presented instead with the A and the B entries.
column sampling methods.

Again, it would be unfair to single out a single paper, also because it's not exactly clear which model you're working in: best to google 'norm estimation' or 'column sampling' to find some of the related results. This survey by Mahoney is a useful reference for sampling methods.

If you have an efficient way of multiplying two matrices (sparse or dense), then frobenius norm should be equal to:

$\| A \|_F = sum(diagonal(A^T \times A))$


Justifying asymptotic worst-case analysis to scientists I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution & ecology, with the goal of being interesting/useful to biologists. One of the biggest difficulties I've faced is in justifying the usefulness of asymptotic worst-case analysis for lower bounds. Are there any article length references that justify lower bounds and asymptotic worst-case analysis to a scientific audience?
I am really looking for a good reference that I can defer to in my writing instead of having to go through the justifications in the limited space I have available (since that is not the central point of the article). I am also aware of other kinds and paradigms of analysis, so I am not seeking a reference that says worst-case is the "best" analysis (since there are settings when it very much isn't), but that it isn't completeletely useless: it can still gives us theoretically useful insights into the behavior of actual algorithms on actual inputs. It is also important the writing is targeted at general scientists and not just engineers, mathematicians, or computer scientists.
As an example, Tim Roughgarden's essay introducing complexity theory to economists is on the right track for what I want. However, only sections 1 and 2 are relevant (the rest is too economics specific) and the intended audience is a bit more comfortable with theorem-lemma-proof thinking than most scientists[1].

Details
In the context of adaptive dynamics in evolution, I've met two specific types of resistance from theoretical biologists:
[A] "Why should I care about behavior for arbitrary $n$? I already know that the genome has $n = 3*10^9$ base pairs (or maybe $n = 2*10^4$ genes) and no more."
This is relatively easy to brush-off with the the argument of "we can imagine waiting for $10^9$ seconds, but not $2^{10^9}$". But, a more intricate argument might say that "sure, you say you care about only a specific $n$, but your theories never use this fact, they just use that it is large but finite, and it is your theory that we are studying with asymptotic analysis".
[B] "But you only showed that this is hard by building this specific landscape with these gadgets. Why should I care about this instead of the average?"
This is a more difficult critique to address, because a lot of the tools people commonly use in this field are coming from statistical physics where it is often safe to assume a uniform (or other specific simple) distribution. But biology is "physics with history" and almost everything isn't at equilibrium or 'typical', and empirical knowledge is insufficient to justify assumptions about distributions over input. In other words, I want an argument similar to that used against uniform distribution average-case analysis in software engineering: "we model the algorithm, we can't construct a reasonable model of how the user will interact with the algorithm or what their distribuition of inputs will be; that is for psychologists or end users, not us." Except in this case, the science isn't at a position where the equivalent of 'psychologists or end users' exists to figure out the underlying distributions (or if that is even meaningful).
Notes and related questions

The link discusses cognitive sciences, but the mindset is similar in biology. If your browse through Evolution or Journal of Theoretical Biology, you will seldom see theorem-lemma-proof, and when you do it will typically be just a calculation instead of something like an existence proof or intricate construction.
Paradigms for complexity analysis of algorithms
Other kinds of running time analysis besides worst-case, average-case, etc?
Ecology and evolution through the algorithmic lens
Why economists should care about computational complexity

My personal (and biased) take is that asymptotic worst-case analysis is a historical stepping stone to more practically useful kinds of analysis.  It therefore seems hard to justify to practitioners.

Proving bounds for the worst case is often easier than proving bounds for even "nice" definitions of average case.  Asymptotic analysis is also often much easier than proving reasonably tight bounds.  Worst-case asymptotic analysis is therefore a great place to start.

The work of Daniel Spielman and Shanghua Teng on smoothed analysis of Simplex seems to me a harbinger of what can happen when we start to gain a better understanding of the shape of a problem: tackling the worst-case first enables a more nuanced understanding to be developed.  Further, as Aaron Roth suggested in the comments, if the "usual" behaviour of a system is significantly different from its worst case, then the system is not yet completely specified and more work is needed to improve the model.  So going beyond worst-case generally seems important as a long-term goal.

As far as asymptotic analysis is concerned, it usually serves to keep a long and messy proof clear of distracting details.  Unfortunately there currently does not seem to be a way to reward the tedious work of filling in the details to obtain the actual constants, so that seldom seems to get done.  (Page limits also work against this.)  Careful analysis of the details of an asymptotic bound has led to actual algorithms, with good bounds on the constants, so I personally would like to see more of this kind of work.  Perhaps if more proofs were formalised using proof assistant systems, then the constants could be estimated with less additional effort.  (Or bounds on the constants, along the lines of Gowers' bound for the Szemerédi Regularity Lemma, might become more routine.)  There are also ways to prove lower bounds that are free of constants, by using more explicit machine models (such as deterministic finite-state automata).  However, such (near-)exact lower bounds for more general models of computation may require a lot of work, or be out of reach altogether.  This seems to have been pursued in ~1958–73 during the first heyday of automata theory, but as far as I can tell has since largely been left alone.

In short: in future, I think we'll see worst-case analysis as just a first step, and I hope we'll see expressions like $O$*$(n^k)$ with galactic hidden constants as just the first step.  I find it difficult to justify the current focus on worst-case asymptotic analysis to practitioners, but perhaps it is useful to see this as the beginning steps of a longer journey.

much agreed this an important topic to survey/cover but it seems not to have been much yet. a few refs of varying style/coverage/audience/ formality not exactly as requested but somewhat close (best seen online so far on medium search, hope to hear further of any better ones; more notes below):

The complexity of algorithms Atkinson (alas only a single ref to biology in the paper, but may suffice on more general science/engineering terms)

The modern theory of algorithms dates from the late 1960s when the
method of asymptotic execution time measurement began to be used. It
is argued that the subject has both an engineering and scientiﬁc wing.
The engineering wing consists of well-understood design methodologies
while the scientiﬁc wing is concerned with theoretical underpinnings. The
key issues of both wings are surveyed. Finally some personal opinions on
where the subject will go next are oﬀered.

Complexity and Algorithms J. Diaz. 100 slides. broad; one could excerpt relevant ones in particular.

A Gentle Introduction to Algorithm Complexity Analysis Dionysis "dionyziz" Zindros

in other words is there a sort of introduction/survey/overview of the complexity theoretic lens in close combination/conjunction/companion with the advancing algorithmic lens in science, something like "Complexity theory for scientists, engineers, and researchers"?
there are good refs on the former "algorithmic lens" you have cited eg Papadimitriou but it does not seem a highly satisfactory ref by an expert in the field has been written on the latter "complexity lens"... yet (maybe some "elite" member of this site will consider that as their next book or paper project).
note also there are a lot of refs on relevance P vs NP outside of complexity theory & in other scientific fields that could be used somewhat for these purpose. will add them in comments if there is any interest.


Positive topological ordering, take 3 Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix?

This question is motivated by this problem:
Positive topological ordering

The original decision problem is at least as hard as this one, so an NP-completeness result would solve that too.

Edit:
Laszlo Vegh and Andras Frank called my attention to an equivalent problem asked by Gunter Rote:
http://lemon.cs.elte.hu/egres/open/Graphs_extendable_to_a_uniquely_matchable_bipartite_graph

Edit:
The reduction to the original problem is as follows. Suppose that the DAG has only two levels, these will correspond to the rows and columns of the matrix. Also, we have one single node with weight +1. Everyone else in the lower level has weight -1 and on the upper level +1.

The problem turned out to be NP-complete. You can read more in detail here and here. Short summary:

The reduction is from a problem was shown to be NP-complete by Dasgupta, Jiang, Kannan, Li, and Sweedyk: given a bipartite graph G and an integer k, decide if G has an induced subgraph on 2k nodes that can be extended to be uniquely matchable. It was observed by Stéphane Vialette that this reduces to the bipartite unique matching version of this problem if we add n-k isolated nodes to both classes.

The problem is NP-complete but where is the algorithm to solve it ? I have one algorithm that works on many examples, but I can't demonstrate its going to work all the time.


Complexity of listing all minimal cut sets / connected 2-partitions of a graph I am trying to find an algorithm that would give me for a given graph all minimal cut sets or equivalently all ways to partition the graph in two connected components. I am searching for an algorithm that ideally would have the complexity linear in the number of cut sets, however, I only find papers describing algorithms that would generate all minimal cut sets between a fixed vertex pair. I would then have to run any algorithm for each pair and remove duplicates, so I am searching for a better approach. Does someone of you know any upper/lower bounds of the complexity of this problem (or even better, an optimal algorithm)? I would also be interested in results concerning special graphs, e.g. max degree k or so.

Best,
Vany

dear all. There is no contradiction here. The problem of listing or enumerating all cutsets is a counting problem which is #P-hard. The class #P consists of all the problems that can be solved by a non-deterministic counting Turing machine in polynomial time. Therefore, the class #P is useful for classifying counting problems. On the other hand, the class NP is suitable for classifying  decision problems. A decision version of your problem would be, for instance: Is there a cutset with cardinality less than $k$? Obviously, if you can enumerate all the cutsets in polynomial time, then you can also say in polynomial time if there exists a cutset with cardinality less than $k$. In other words, the counting version is at least as hard as the decision version.  Therefore, if a counting problem is #P-hard, then it is NP-hard (I am talking about the same counting problem, not its decision version). However, the converse is an open question. In other words, for the time being, saying that this problem is #P-hard is a stronger statement than saying that it is NP-hard.


Formal notion for energy complexity of computational problems Computational complexity includes the study of time or space complexity of computational problems. From the the perspective of mobile computing, energy is very valuable computational resource. So, Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms. Also, Are there established energy-complexity classes for computational problems?

References are appreciated.

Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms?  No!

But maybe you could come up with one. It's possible you could divide the Turing machine steps into reversible and non-reversible (the non-reversible ones are where information is lost). Theoretically, it is only the non-reversible steps that cost energy. A cost of one unit of energy for each bit that is erased would theoretically be the right measure.

There is a theorem of Charles Bennett that the time complexity increases by at most a constant when a computation is made reversible (C.H. Bennett, Logical Reversibility of Computation), but if there are also limits on space, then making the computational reversible might incur a substantial increase in time (Reference here). Landauer's principle says that erasing a bit costs $kT\, \ln 2$ of energy, where $T$ is temperature and $k$ is Boltzmann's constant. In real life, you cannot come anywhere close to achieving this minimum. However, you can build chips which perform reversible steps using substantially less energy than they use for irreversible steps. If you give reversible steps a cost of $\alpha$ and irreversible steps a cost of $\beta$, this seems like it may give a reasonable theoretical model.

I don't know how Turing machines with some reversible steps relate to chips with some reversible circuitry, but I think both models are worth investigating.

Time and space complexities are device independent. I don't see a way to make energy-complexity device independent.

If $W$ is work done by a Turing machine to perform one basic step. Then energy complexity becomes number of steps times $W$. $W$ is highly machine dependent.

And, $O(W f(n)) = O(f(n))$.


Computing Functions with Dynamical Systems I was trying to make a set of differential equations "compute" some given function just like a Turing Machine does. Essentially, a given Turing Machine with an initial configuration (which includes all initial conditions - The initial tape content, starting state, initial head position) "evolves" to a specific configuration after a finite number of steps and if the function is computable, it halts with the output of the function on the tape. I am trying to draw an analogy of Turing Machines with other "time-evolving" systems and the most intuitive of all is a Dynamical System as a set of differential equations. As an attempt, I formulated a dynamical system which could compute asymptotically the square of a number.

Suppose I want to find the functions $f(x,y,t)$ and $g(x,y,t)$ such that the following dynamical system:

$\frac{dx}{dt}=f(x,y,t)$

$\frac{dy}{dt}=g(x,y,t)$

is such that:

In the phase plane (with $x$ on X axis and $y$ on Y axis), every point on the X axis is a fixed point.
Any initial point on the line y=$\alpha$ (with $\alpha\neq0 $) with coordinates $(x(0),\alpha)$ goes towards the fixed point $(x(0)^2,0)$ for $t\rightarrow\infty$

The functions $f$ and $g$ may contain the $\alpha$ term

With such a dynamical system at hand, if we wanted to compute the square of a number $a$, all we have to do is to start off with initial conditions $x(0)=a$ and $y(0)=\alpha$ (Just like we place the initial input on the Turing Machine's tape,set the initial state to the starting state and correctly position the head; In this case we place the input $a$ as the x coordinate of the initial point of the phase trajectory) and "let the Dynamical System evolve" (Just like we let the Turing Machine evolve after placing the inputs), the phase trajectory will converge to $a^2$ for $t\rightarrow\infty$ (Assuming the function to be computable, the turing machine stops in finite time and it prints the output on tape; the given dynamical system doesn't stop in finite time but it also "prints the output" as the x coordinate of the evolved phase trajectory for $t\rightarrow\infty$). In other words if we had a "machine M" following the given dynamical system, we could say that: M computes the "square" function asymptotically. (Just like the way the turing machine computes the "square" function in finite time) The computations in this case happens over reals as opposed to that over members of a countable alphabet.

But I cant really think of such functions $f$ and $g$ for computing the "square" function and I need help finding these. Furthermore if I start taking up more complicated functions to compute, finding the corresponding $f$ and $g$ will not be a trivial task. Can someone guide me on what possible difficulties I may face and how I can overcome them?

If I can formulate computation using Dynamical Systems the way I described above, is there a possibility to prove some theorems in computability (and complexity?) using these formulations?

Thankyou!

Brockett [1] studied a closely related idea, and showed how to construct dynamical systems that solve any linear programming problem in (I believe) the same manner you suggest, as well as dynamical systems to sort a list of numbers and to diagonalize a matrix. You may be able to use this to directly get the dynamics you need to compute the squaring function.

(At some point I saw a cool video of the trajectory of a dynamical system for sorting, but I can't seem to find it...)

I won't venture a guess as to whether such dynamical systems formulations could be used to prove something interesting in computability/complexity, but can offer some further references that may be relevant.

In quantum computing, Nielsen, Dowling, Gu, and Doherty show that QC can be realized as (if I understand correctly) geodesic flow on a certain manifold - a particular example of the kind of dynamical system you're talking about. See [2] and references therein for a discussion of some complexity issues related to this.

Finally, although I don't think it's exactly what you're talking about, it would probably also be worth checking out Bernard Chazelle's work on "influence systems" which are a type of dynamical system that is at least as powerful as Markov chains and Turing machines, but can exhibit all kinds of dynamic behavior (including chaos, etc). See [3] and references therein.

[1] Roger W. Brockett, Dynamical Systems that Sort Lists, Diagonalize Matrices and Solve Linear Programming Problems, Proc. 27th IEEE Conf. Dec. and Control, Austin, TX, pp. 799-803, Dec. 1988.

[2] Mark R. Dowling, Michael A. Nielsen. The geometry of quantum computation, arXiv:quant-ph/0701004, 2007.

[3] B. Chazelle, Natural Algorithms and Influence Systems, Comm. ACM 55 (2012), 101-110.

here are two other references that show the connection between physics/dynamical systems theory and undecidability (and therefore Turing completeness). therefore being TM complete, all computable functions are representable/reducible to these systems.

the 1st ref uses the physics laws of classical mechanics, which can be described as differential equations (eg Newtons law etc). the descriptions below are from Wikipedia. a description from Ian Stewarts book From here to infinity [the key statement wrt your question is about dynamic system trajectories which are governed by differential equations]:

  Recent work of Newton da Costa and F.A. Doria casts doubt upon Penrose's thesis, and explores the limits of computability in chaotic classical dynamical systems. They show that undecidability extends to many basic questions in dynamical systems theory. These include whether the dynamics is chaotic, whether a trajectory starting from a given initial point eventually passes through some specific region of phase space, and whether the equations are integrable—that is, possess an explicit solution defined by formulas built up from classical functions such as polynomials, sines, and exponentials. Indeed virtuallly any 'interesting' question about dynamical systems is—in general—undecidable.

N. C. A. da Costa and F. A. Dória, Undecidability and incompleteness in classical mechanics, Int. J. Theor. Physics vol. 30, pp. 1041-1073 (1991)

  Proves that chaos theory is undecidable and, if axiomatized within set theory, incomplete in the sense of Gödel.

N. C. A. da Costa and F. A. Dória, An undecidable Hopf bifurcation with an undecidable fixed point, Int. J. Theor. Physics vol. 33, pp. 1885-1903 (1994).

  Settles a question raised by V. I. Arnold in the list of problems drawn up at the 1974 American Mathematical Society Symposium on the Hilbert Problems: is the stability problem for stationary points algorithmically decidable?
  I. Stewart, ``Deciding the undecidable, Nature vol. 352, pp. 664-665 (1991).


Finding a cutting plane that splits a polyhedron evenly Say we have a polyhedron in standard form:

\begin{equation*}
\begin{array}{rl}
\mathbf{A}\mathbf{x} = \mathbf{b} \\\\
\mathbf{x} \ge 0
\end{array}
\end{equation*}

Are there any known methods for finding a hyperplane $\mathbf{d} \mathbf{x} +d_0= 0$ that splits the polyhedron in a way that the number of vertices on each side of the hyperplane is approximately the same?  (i.e. an algorithm that minimizes the absolute difference of vertex cardinalities on the two sides of the split).

Also, are there any known results regarding the complexity of this problem?

Addendum: Restricting the types of cuts:

Here is a variation of the original problem with the hope that it is easier to solve than the original one:

Is there a way to efficiently compute or estimate for which coordinate $i$ a hyperplane of the form $d_ix_i + d_0 = 0$ would yield the lowest absolute difference of vertex cardinalities on both sides of the split? By efficient I mean anything more efficient than the exhaustive enumeration of vertex cardinalities for all  possible such splits.

Note: After a few days of little progress, I posted this question at MathOverflow too.

I can't remember the analytic way to do this!

But this a classical problem for Genetic Programming! If you are familiar with it you can use a normalized vectors in the center of the polyhedron that describes the cutting plane.

So your population is a set of [x,y,z,...] normalized vectors and as fitting function you use the difference between the 2 split volumes!

So, if the difference tends to zero more "fit" is your vector/plane!