title: Multiplication in $O(n\cdot \log n)$

text:
# Question
Title: Multiplication in $O(n\cdot \log n)$
I was looking in here, and I noticed the best runtime for multiplication of two $n$-bits numbers is $O(n\cdot \log n \cdot 2^{O(\log^\* n)}$, but I can easily notice an algorithm that runs in $O(n\cdot \log n)$.

After all, we know how to multiply two polynomials from degree $n$ in $O(n \log n)$ runtime. But multiplying polynomials is the same as multiplying two $n$-bits numbers. So we have an algorithm to multiply two $n$-bits numbers in $O(n \log n )$. Now the only problem that might occur is the carry, but in each phase we can fix that in $O(n)$ time, simply moving on the rightest bit and its left-neighbour, until the end. That is, our runtime shall remain $O(n \cdot \log n)$.

So did I make a new (and pretty obvious) discovery? Or is the wikipedia page out of date? Or perhaps I have some mistake?

# Answer
> 8 votes
As @DavidRicherby already points out, the confusion arises because different measures of complexity are getting mixed up. But let me elaborate a bit.

Usually, when studying algorithms for polynomial multiplication over arbitrary rings, one is interested in the number of arithmetic operations in the ring that an algorithm uses. In particular, given some (commutative, unitary) ring $R$, and two polynomials $f,g \in R\[X\]$ of degree less than $n$, the Schönhage-Strassen algorithm needs $O(n \log{n} \log{\log{n}})$ multiplications and additions in $R$ in order to compute $fg \in R\[X\]$ by, roughly, adjoining $n$-th primitive roots of unity to $R$ to get some larger ring $D \supset R$ and then, using the Fast Fourier Transform over $D$, computing the product in $D$.

If your ring contains an $n$-th root of unity, then this can be sped up to $O(n \log n)$ operations in $R$ by using the Fast Fourier Transform directly over $R$. More specifically, over $\mathbb{Z} \subset \mathbb{C}$, you can do this using $O(n \log n)$ ring operations (ignoring the fact that this would require exact arithmetic over the complex numbers).

The other measure that can be taken into account is the bit complexity of an operation. And this is what we are interested in when multiplying two integers of bit length $n$. Here, the primitive operations are multiplying and adding two digits (with carry). So, when multiplying two polynomials over $\mathbb{Z}$, you actually need to take into account the fact that the numbers that arise during computation cannot be multiplied using a constant number of primitive operations. This and the fact that $\mathbb{Z}$ doesn't have an $n$-th primitive root of unity for $n \> 2$ prevents you from appling the $O(n \log n)$ algorithm. You overcome this by considering $f,g$ with coefficients from the ring $\mathbb{Z}/\langle 2^n + 1 \rangle$, since the coefficients of the product polynomial will not exceed this bound. There (when $n$ is a power of two), you have (the congruence class of) $2$ as an $n$-th root of unity, and by recursively calling the algorithm for coefficient multiplications, you can achieve a total of $O(n \log n \log \log n)$ primitive (i.e., bit) operations. This then carries over to integer multiplication.

For an example that nicely highlights the importance of the difference between ring operations and primitive operations, consider two methods for evaluating polynomials: Horner's method and Estrin's method. Horner's method evaluates a polynomial $f = \sum\_{i=0}^n f\_i X^i$ at some $x \in \mathbb{Z}$ by exploiting the identity $$f(x) = (\ldots (f\_n x + f\_{n-1})x + \ldots + \ldots) + f\_0$$ while Estrin's method splits up $f$ into two parts $$H = \sum\_{i=1}^{n/2} f\_{n/2+i} X^i$$ and $$L = \sum\_{i=0}^{n/2} f\_{i} X^i$$ i.e., $H$ contains the terms of degree $\>n/2$ and $L$ the terms of degree $\leq n/2$ (assume $n$ is a power of two, for simplicity).

Then, we can calculate $f(x)$ using $$f(x) = H(x)x^{n/2} + L(x)$$ and applying the algorithm recursively.

The former, using $n$ additions and multiplications, is proven to be optimal w.r.t. the number of additions and multiplications (that is, ring operations), the latter needs more (at least $n + \log n$).

But, on the level of bit operations, one can (quite easily) show that in the worst case, Horner's method performs $n/2$ multiplications of numbers of size at least $n/2$, leading to $\Omega(n^2)$ many bit operations (this holds even if we assume that two $n$-bit numbers can be multiplied in time $O(n)$), whereas Estrin's scheme uses $O(n \log^c n) = \tilde{O}(n)$ operations for some $c \> 0$, which is, by far, asymptotically faster.

# Answer
> 9 votes
Saying that you can multiply two polynomials of degree $n$ in time $O(n\log n)$ implies that, in particular, you can multiply degree-zero polynomials, i.e., constants, in constant time. Clearly, therefore, the claims "multiplying $n$-bit numbers takes time $O(2^{\log^\*n}n\log n)$" and "multiplying degree-$n$ polynomials takes time $O(n\log n)$" are relative to different models of computation so are not directly comparable.

---
Tags: runtime-analysis
---


# Question
Title: Do Turing machines assume something infinite at some point?
In a previous question What exactly is an algorithm?, I asked whether having an "algorithm" that returns the value of a function based on an array of precomputed values was an algorithm.

One of the answers that caught my attention was this one:

> The factorial example gets into a different model of computation, called non-uniform computation. A Turing Machine is an example of a uniform model of computation: It has a single, finite description, and works for inputs of arbitrarily large size. In other words, there exists a TM that solves the problem for all input sizes.
>
> Now, we could instead consider computation as follows: For each input size, there exists a TM (or some other computational device) that solves the problem. This is a very different question. Notice that a single TM cannot store the factorial of every single integer, since the TM has a finite description. However, we can make a TM (or a program in C) that stores the factorials of all numbers below 1000. Then, we can make a program that stores the factorials of all numbers between 1000 and 10000. And so on.

Doesn't every TM actually assume some way to deal with infinity? I mean, even a TM with a finite description that computers the factorial of any number N through the algorithm

```
 int fact(int n)
 {
 int r = 1;
 for(int i=2;i<=n;i++)
 r = r*i;
 return r;
 }

```

contains the assumption that a TM has the "hardware" to compare numbers of arbitrary size through the "\<=" comparator, and also ADDers to increment i up to an arbitrary number, **moreover**, the capability of representing numbers of arbitrary size.

Am I missing something? Why is the approach that I presented in my other question less feasible with respect to infinity than this one?

# Answer
A Turing machine does *not* have the ability "to compare numbers of arbitrary size through the `<=` comparator" because a Turing machine does not have a "`<=` comparator". A Turing machine has a fixed, finite set $Q$ of states and a fixed, finite tape alphabet $\Sigma$. At each step of the computation, the Turing machine looks at its current state and the symbol under its read/write head and decides what to do next: which state to enter, which symbol to write to the tape and which way to move the tape head.

Because of this, a Turing machine cannot compare arbitrarily large numbers in a single `<=` instruction. Using the state, it can remember at most $|Q|$ different numbers and, using the alphabet, it can write at most $|\Sigma|$ different numbers in a single tape cell (using each possible symbol to represent one number). As such, to compare arbitrarily large numbers on a Turing machine, you must write each number as a sequence of digits on the tape and write an algorithm that will take multiple steps to compare those two numbers. As you can imagine, this makes writing Turing machine programs a rather fiddly endeavour.

Turing machines don't really "deal with infinity": they deal with unbounded finite things, at least in their standard definition. The input is a finite string and, after any finite number of steps, the machine has only examined or written to a finite number of tape cells. There is no bound on the size of the input or the number of computation steps but, the input is finite and, after any finite number of steps, only a finite amount of output has been produced.
> 9 votes

# Answer
I think the important distinction to make is that the description of the Turing machine is finite, as is the input to the machine, while the tape it uses as memory is infinite. The TM is is a mostly finite machine, which uses a finite tape. Consider the tape to be composed of cells, where each cell can contain a single value. The input to the TM is written on the tape.

The description of a TM is a finite set of tuples `<current state, input, output, move, next state>`.

At each step, the thing to be done is found by matching the current state and input. Eg, we are in state 0, and we read a 1, so we find the tuple that begins `<0, 1, ...>` then we write a new value in the current cell, move left or right (I think the classic definition also allows for staying at the same cell as well), and then change to a new state.

So, for your example, you would either need an infinitely large description of the TM (an infinite number of `<current state, input, output, move, next state>` tuples), or include the lookup information in the input to the TM. I believe the input to a TM is defined to be finite. So, that's probably not something you could do with a classically defined Turing machine.

The Fibonacci example, in contrast, can be computed in binary with a finite number of tuples to describe the TM, and has a finite input.
> 7 votes

# Answer
**In a nutshell**: Turing Machine can do (finitely specified) infinite computations on (finitely specified) infinite data and produce (finitely specified) infinite results. The basic idea is that those infinities can be defined as the limit of finite entities, defined in a mathematically appropriate way. This is the basis of mathematical semantics of computation. If you consider programs rather than Turing Machines, these programs can also contain (finitely specified) infinite data-structures. The case of a tabulated function `fact` as a possible algorithm is analyzed in the end, as a program, or as a TM model, with a hint regarding the relation with lazy evaluation of infinite objects.

## With many more details

Regarding your final question, a TM does not compute on arbitrary numbers, but on symbolic representation of these numbers as arbitrarily (unbounded) long strings of symbols representing them. Modulo proper encoding, it is correct that they can compare or do arithmetics with such numbers through these representations.

But the original question is about the role of infinity in Turing Machines in general.

A common answer to this question is that Turing Machines never deal with infinity. They are finitely defined, and whatever they compute is computed in finite time on a finite part of the tape (hence a finite tape that is larger would be enough). What is true is that the time of space requirement of the TM are unbounded, which is not the same as infinite.

Hence, any answer that is computed by a TM could be computed as well by a finite-state automaton (FSA), which is "to some extent" one way to look at tabulation. The difficulty there is that some input sizes (it nearly always comes to that, if only to read the input) will exceed the size of the automaton. But then, we can just use a bigger one. So if we want to consider unbounded input size, we need an infinite sequence of FSA that can do the computation. Actually we may need a finite-state machine a bit more complex than the traditional FSA since there may be an output to be computed (rather than a yes-no answer), but a finite state transducer should probably do.

So, if we are looking at a problem that has an infinite set of instances, such as computing a GCD, or simply using arithmetics on integers of arbitrary size, we see that infinity is coming back at us through the back door, as this infinite set of FSA.

But there is another problem. The above analysis works only when we consider computations that do terminate with a result. But not all TM do that. Some may enumerate the members of an infinite set. This is typically the case for a TM that computes the decimals of $\pi$ and keep adding new one, indefinitely. Of course, it computes only a finite answer in a finite time, but what we are interested in is really the infinite sequence produced by an infinite computation. Notice that we now have two aspects of infinity: infinity of computation, and infinity of the result (i.e. of some computed data). Actually that could even lead to considering infinite input ... but let us ignore this complication, that deals with unbounded streams of data. Note also that such computations that give an output other than yes

Then again, we can replace that by an infinite sequence of finite computations with finite machines. But are we cheating.

From a physical point of view, that is the best we can do. We only know how to build finite machines, at least according to the current state of the art in physics, which is not expected to change too much on that issue in the near future.

But how can we handle those infinities in a consistent and tractable way from a mathematical point of view.

When you consider an infinite set of FSA that can sort of cooperate to compute an infinite set of answers, you cannot do it arbitrarily. You need some safeguards to ensure that what you are doing makes sense. It is well known that you can trivially build any set with an infinite union of regular sets, actually with an infinite union of singleton sets. So, considering arbitrary infinite unions of automata without any restriction will lead you nowhere. You even consider in the same set automata that give you inconsistent answers.

What you really want is define a notion of consistency. But that requires some precautions. Let us assume you are using an infinite sequence of automata to simulate a TM that answer yes or no, or does not halt. The problem is that a FSA will always halt with an answer, such as yes or no. But if you use a FSA that is actually not sized big enough for the chosen input, what should it answer. Both yes and no are reserved for the cases when the FSA actually terminated the TM computation, and using one of these answer with an unfinished computation would only lead to confusion. What you want is an answer that says: "*sorry, I am too small and I cannot tell. Please try with a bigger guy in the family*". In other word you want an answer such as *overflow*, or *don't know*. Actually it is called by semanticians "*undefined*" or also "*bottom*" and often written "$\bot$".

So you need automata that have 3 sorts of states: accepting, non-accepting, and undefined. An undefined state may be viewed as a state standing for a missing part of the automaton that forces computation to stop. So, when computation halts, depending on the state it halts on, you get the answer *yes*, *no*, or *undefined*.

Now, you see that what you want is **infinite sequences of automata that are consistent**. Both *yes* and *no* are consistent with *undefined*, but *yes* is not consistent with *no*. Then two automata are consistent when they give consistent answers on the same input.

This can be extended to automata that compute other kind of answers. For example if they compute colors, such as red, blue, green ..., you can add the undefined color which is consistent with all others. If the answer is an infinite sequence of digits such as those of $\pi$, then each digit can be consistently and independently replaced by undefined so that $3.14\bot\bot\bot\bot...$ is consistent with $3.1415\bot\bot\bot\bot...$ and with $\bot.\bot5159\bot\bot\bot\bot...$, but the latter two are not consistent with $3.1416\bot\bot\bot\bot...$. Actually, in this sense, $3.1416\bot\bot\bot\bot...$ is not an approximation of $\pi$. We say that an answer is better defined than another when it contains all the information that can be found in the other one, and possibly more. This is actually a partial ordering.

I will not develop further these theoretical aspects, which is a bit awkward when based on Turing Machines. The point is that these concepts lead to the idea that computation domains (whether data or machines), form mathematical structures such as lattices, in which infinite object can be adequately defined as the limits of infinitely increasing (i.e. better and better defined) sequences of finite objects. Defining the infinite sequences requires some more apparatus, and a notion of continuity. This is fundamentally what Dana Scott's theory of semantics is about, and it gives a somewhat different view of the concepts of computability.

Then, Turing machines, or other formal devices that can do "infinite computation" can be defined as limits of sequences of finite approximations of the machines, that are better and better defined. The same is true for whatever data the machines compute with, whether input or output.

The simplest document I ever read on this is a hand-written set of lecture notes by Dana Scott, often referred to as the Amsterdam lecture notes. But I could not find it on the web. Any pointer to a copy (even incomplete, as I have part of it) would be welcome. But you can look at other early publications by Scott such as *Outline of a Mathematical Theory of Computation*.

## Back to the initial example of the question

These approximation concepts apply to data as well as to programs. The function `fact` is defined recursively, which means that it is the least fixed point of a functional that can be used to compute a sequence converging finite approximation of `fact`. This sequence of more and more defined finite functions converges to an infinite entity that is what you call the function `fact`.

But if you use array lookup, you can do exactly the same, with your code containing larger and larger tables which are all finite approximations of the infinite table of precomputed values of `fact`. Each of these array can actually give an answer for any integer, but the answer can be $\bot$ (*undefined*) when the table is not defined enough (big enough). The table look-up algorithm too must be defined by a sequence of approximations, as it computes with an infinite table.

It is true that, if you consider the elementary TM model of computation, such an infinite array cannot be expressed in that formalism. It does not mean that it would not make sense. A Turing machine could have a second tape that is supposed to be initialized with the tabulated values of some functions such as `fact`. It does not change the computational power of the TM, as long as that function is a computable one, i.e. as long as the table can be initialized with an infinite computation of another TM that can compute all argument-value pairs for the relevant function.

But in practice, you cannot complete an infinite computation. Hence the right way to do it is to compute the table lazily, i.e. to fill entries only when needed. That is precisely what is done with memoization, which is the answer I gave you, with different justifications, for your previous question.
> 5 votes

# Answer
**The gist of this answer is that Turing Machines can mimic anything we can program, and we do program computations on, with and of infinite objects.**

This is a second answer focussing more on the specific question asked than on the general theoretical framework that justifies the answer, and would be definitively needed to answer the more general title of the question. It is fully compatible with my previous answers to the OP's questions, both *What exactly is an algorithm?* and *Do turing machines assume something infinite at some point?*, answers in which I developed more the theoretical context. This may be seen as answering both questions.

**Turing machines do have the ability to deal with infinity**, as can all Turing complete computational models, though only with denumerable infinity. Our problem is that we can observe only part of this infinity, but we have to consider the whole of it since the part we may observe is unbounded.

The other problem is that we can deal ourselves only with finitely specified entities. Actually, the whole structure of science as we know it falls down if we consider entities that are not finitely specified, since it becomes impossible to check consistency of definitions, to even know what the definitions are, since we can access only part of them in a finite time.

There is possibly another fundamental issue that is somewhat similar to the fact that closure under infinite union defines any set you want, unless you can finitely restrict appropriately what is permitted in such a union. But I am not sure I fully understand this issue.

As I said, *Turing machines do have the ability to deal with infinity*. I am contradicting other well upvoted answers of some high rep users, who should know what they talk about on such an elementary topic.

The problem is that Turing chose a very elementary model of computation to achieve his theoretical purpose. The simpler, the better. It is to more advanced/sophisticated models of computation pretty much what machine language is to programming: something very obscure where you cannot recognize any of the concepts that do make sense in high-level programming. The fact is that, like machine language, TM can mimic much more than they can directly express.

Furthermore no one actually believes in these limitations of the Turing Machine, and many varieties of TM have been devised, with more or less exotic features. If some infinite sets are called **recursively enumerable**, it is because TM can actually enumerate (representations of) their members, which does require an infinite computation (see *Turing Machines as Enumerators* in Hopcroft-Ullman 1979, page 167). Of course, we can always encode that as finite computations that would answer questions such as: *what is the $23{rd}$ member of the set according to your enumeration of them?* But it would still be often implemented as an infinite computation that is artificially stopped when the right answer is attained.

Actually, all users who state that everything is finite but unbounded in a TM are quite careful to add that they consider *Turing Machines in their standard definition*. The problem is that the standard definition is just a device to simplify the theory, but is pretty much irrelevant when trying to understand computational structures.

Actually, **the only thing that matters in computation is that everything must be finitely specified in a computable way, not that it be finite**.

We are assuming that a turing machine must be a finite object. But that is not true. You can define a model of Turing machine using a second tape that is read only, and contains a function tabulated for all integer values, without any bound. That is infinite. But it does not buy you any extra computing power as long as the content of that tape is computatbly specified (the computability implies that it is finitely specified). The extra tape could well be replaced by a TM machine embedded in the other one, and would provide the answers, instead of looking for them on the extra tape. From a higher level, the difference is not visible.

From a practical realization point of view, we could have a `fact` turing machine computing factorials and tabulating them on the extra tape, while another TM would used the tabulated factorial from the extra tape, just waiting on the first TM whenever the tabulation has some still missing entry. But the second machine does assume that the content of the tape is ultimately infinite. The tabulating machine does not even have to work all the time, but must resume computation whenever data is requested from the table and is not found there.

Coming back to the question, the main difference between unbounded integers and the infinite table is only that integers are finite, unbounded but completely computed in finite time. The infinite table is computed indefinitely, finite but still growing all the time to infinity. That is not a problem, but is a difference. Infinite objects are accessible only through finite approximations, ... but they are infinite. Computable irrational numbers are, in this sense, infinite objects, at least for their representation as binary numbers.

All algorithms are defined in the context of some mathematical theory. And a table look-up together with an infinite table is an algorithm. But it is an algorithm in a mathematical theory having a finitely defined infinite set of axioms that specify extensively (rather than intensively) the values of a function it axiomatizes for each integer argument. (see my answer to your previous question). Then it is always legitimate to do so, as you can always add provably true statements to the axioms of a theory.

**Usul statements, as reproduced in your current question, is in my opinion incorrect** (though everything is also a matter of definition). His conclusion in his answer, that you did not reproduce, is that the use of an infinite table cannot be considered an algorithm because it can only be implemented by a non-uniform model of computation, by a collection of different machines, and hence such uses "*do not have a finite description that can be implemented to solve the "whole" problem for any input size*". This is wrong. His partitioning into disjoint machines that have separate domains of definition is just a wrong way to do things. The right way is to have an infinite sequence of consistent machines with larger and larger domains of definition, which can appropriately converge to the infinite machine that answers the question. That is one essential purpose of the mathematical theory of semantics of computation defined by Dana Scott. With proper mathematical apparatus, it does define precisely infinite machines, values with infinite representations (such as *e* or $\pi$), or infinite data structures, that are all computable. (see my first answer to this question).

The way such infinite entities are computed with in practice is by means of lazy evaluation, computing just whatever part is needed at any time, and resuming the computation for some of the rest whenever more becomes needed. That is exactly what is proposed above with the `fact` machine lazily computing factorial to be stored in a table, whenever more data is needed from the table.

In a way, that seems to vindicate the assertion (in DanielV's answer) that the codespace must be finite, since lazy evaluation will be actually based on some finite code. But computability is a pervasive game of encoding, so that, among other things, distinguishing code from data is always pretty much in the eyes of the beholder. Indeed, many modern programming languages do not make much difference between intensional and extensional specification of values, and Denotational Semantics does not really distinguish "2+2" from "4". Semantics is really what we are talking about when asking a question such as "*What is **X**?*".

This view of the finiteness of code, also seen as static, is another reason why an infinite table (considered as part of the code) is not seen on an equal footing with unbounded integers used as data. But that is another illusion that does not survive known programming practice in metaprogramming, reflexive languages, and the use of the `eval`function. In those languages, code can be extended without bounds by the running program itself, as long as the computer is running. Indeed one could consider Turing Machines that modify their own transition rules, increasing their number without bound. That is pretty close to the way Universal Turing machines are working.

When designing theoretical frameworks, there is always a tension between simplicity and perspicuity or expressivity. Simplicity make analysis of the framework often simpler, especially when it come to proving specific properties or reducing it to other frameworks. But it is often inconvenient for expressing high level concepts that must then be encoded. We do not program with Turing Machines, but with high level languages that are a lot more expressive and perspicuous, and may at the same time erase some barriers such as the distinction between code and data, on the basis of semantic equivalence. Turing machines seem simple, but can go far beyond their elementary definition.
> 3 votes

# Answer
The short answer: *no*. Turing machines do *not* assume anything infinite at any point.

This is one reason why they are valid as a model for computation. It doesn't make sense to describe computation as something performed by an infinite device.

However, their *operation* may be infinite: it may not terminate. This is another reason why they are valid as a model for computation. Devices that can only perform operations which are guaranteed to always terminate cannot express all possible computations.

What is more: operation requires *unbounded* memory: while the actual amount of memory in use is always finite, it may grow arbitrarily large. So you can't supply all the memory any operation will ever need in advance. Devices that can only perform operations which are guaranteed to never use more than a certain fixed amount of memory cannot express all possible computations.
> 3 votes

# Answer
"thinking out of the box" and generalizing on this question that does get to some heart of the abstraction of Turing machines, and coming up with a different angle not already answered: yes, Turing machines have some intrinsic aspects of "assuming infinities" just as the concept is intrinsic to mathematics. TMs are an abstraction of physical machines. the physical concepts of Time and Space are purposely used in TM theory but as abstractions, however also with aspects of their real counterparts.

in short the TM can possibly run forever *in theory*, aka the halting problem. the tape is infinite but only a finite amount of it can ever be written to at a given time. a TM that runs forever basically assumes that time and space are unlimited, ie "infinite". in fact there is a corresponding Time and Space hierarchy / "continuum" that is infinite.

but no physical realization of this abstract concept is possible assuming the physical universe is bounded (space, time, matter, the last of which is somewhat analogous to "symbols" or "ink" in the Turing machine). somewhat similarly/ analogously, in physics sometimes the universe is regarded as unbounded/ infinite, but only as an abstraction. to flip this, that is also why the "modelling" of a modern computer as a Turing machine is itself an abstraction, because the computer can only have finite memory etc.

another useful comparison is the number line in mathematics. the number line is infinite, but it denotes finite numbers. every number on the number line represents a finite quantity, but there an infinite number of these finite quantities. the Turing machine tape has a strong similarity to the number line concept from mathematics. Turing could have easily defined it as only infinite in one direction, but he defined it as infinite in both directions, much like the mathematics number line, with negative positions "left" on the tape and positive positions "right".
> -1 votes

---
Tags: turing-machines, computation-models
---


title: Subset sum algorithm in O(n³ log n)?

text:
# Question
Title: Subset sum algorithm in O(n³ log n)?
I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers.

After my research, I'm lost between all the algorithms for this problem.

* $O(2^N\*N)$ for the naive algorithm (I understand)
* $O(2^{N/2})$ for advanced algorithm (I understand)
* $O(N * C)$ for pseudo-polynomial time algorithm (only positive numbers)

Reference : Wikipedia

* $O(N^3 * log(N))$ for an exact resolution but I don't understand the whole process

Reference : Andrea Bianchini paper

I would like to know if my resolution is in polynomial time ?

If it is, the paper of Andrea Bianchini is too. So it should proove that P=NP, but it's not the case. Why ?

# Answer
This is a common misconception many have. Subset sum, among others, is NP-complete **only if the input is encoded in binary** (or ternary etc). In unary encoding it's polynomial-time solvable by a simple dynamic programming approach. These problems are sometimes referred as weakly NP-complete.
If you're not quite sure what I mean by unary encoding: Unary encoding means we encode a number by a sequence of $1$'s of appropriate length.
All in all, I fear you haven't settled P/NP (unless, of course, your runtime refers to binary-encoded problems). But good luck!
As an example, suppose your input consists of $10$ numbers, each between $128$ and $256$. Then your input size is, in unary, about $10 \times 256=2560$, whereas your input size is, in binary, $10 \times \log\_2 (256) =80$.
That's quite a difference!

Wikipedia describes an algorithm that works in polynomial time for unary encoding. Wikipedia's solution was taken from the book *Computers and Intractability: A Guide to the Theory of NP-Completeness*, by M. Garey and D. Johnson.
> 5 votes

---
Tags: complexity-theory, landau-notation, p-vs-np, knapsack-problems
---


title: PARTITION with 0-sum assumption

text:
# Question
Title: PARTITION with 0-sum assumption
The PARTITION problem: $\\{\\{x\_1,...,x\_n\\}: \exists I\subseteq\[n\], \sum\_{i\in I}x\_i=\sum\_{i\notin I}x\_i\\}$ is well known to be NP-complete.

> My question: does the partition problem remain NP-complete (as a promise-problem) if we are given that $\sum\_{i=1}^n x\_i=0$?.

A problem that arises in this assumption is that one can always take the empty-set, so we also need to require that $I$ is nontrivial.

Note that for the related SUBSET-SUM problem, it is easy to show that the problem remains NP-complete (reduce from subset-sum of positive numbers by adding the negation of the sum).

My guess is that the problem remains NP-complete, but no proof yet.

# Answer
No. The problem is trivial, since taking $I$ to be the empty set always results in a solution to the problem.

Yes, it is NP-complete. Note that if there is a solution, that is

$\Sigma\_{i\in I} x\_i = \Sigma\_{i\not\in I} x\_i$

then

$\Sigma\_{i\in I} x\_i - \Sigma\_{i\not\in I} x\_i = 0$.

Since we have

$\Sigma\_{i\in I} x\_i + \Sigma\_{i\not\in I} x\_i = 0$

then $\Sigma\_{i\not\in I} x\_i = 0$ and $\Sigma\_{i\in I} x\_i = 0$.

Proof of NP-hardness is by reduction from partition. For a given instance of the partition problem, a multiset $S$ of integers, where $\Sigma\_{s\in S}=2N$, create an instance of Partition with 0-SUM, by adding 2 copies of $-N$ to $S$.

Clearly, if the Partition instance has a solution then so does the modified problem, by adding $-N$ to each half of the partition. If the Partition with 0-SUM restriction has a solution, then so does the original Partition problem: since all the integers in the original partition problem are positive, each 0-SUM "half" of the 0-SUM partition must contain one of $-N$, and the rest must sum to $N$.
> 4 votes

---
Tags: complexity-theory, np-complete, np-hard
---


# Question
Title: Conversion from assembly program to low-level machine language
While studying COMPILER-DESIGN through an online book from Google Books, referenced as *Compiler Design* by A.A.Puntambekar, I got stuck across a line. Actually, I am more curious to know the inner-detail.

> The assembler converts the assembly-program to low-level machine language using two passes. A pass means one complete scan of the input program. The end of the second pass is the relocatable machine code.

Why the 2 passes for conversion and what are the phases involved like lexical analysis,syntax analysis,etc while conversion from assembly to machine-code??? I have very less/no idea about it.

If someone over here would like to describe those two-passes or link out to some good resources, I'd be thankful to him/her.

# Answer
> 6 votes
The first pass can't resolve any forward jumps. For example:

```
    cmp r1, 0
    bne label
    add r2, r3, r4

label:
    add r3, r4, r5

```

On the first pass, when the assembler gets to the `bne label` instruction, it doesn't know how far the branch needs to jump because it hasn't seen `label` yet. On the second pass, it knows where all the branch targets are located and therefore it can go ahead and generate the proper branch/jump instructions at that time.

---
Tags: compilers, code-generation
---


# Question
Title: Balanced Weight Distribution in Bins/Buckets
> Let $W = \\{w\_1,w\_2,...w\_n\\}$ be a set of integer weights. Let $B = \\{b\_1,b\_2,...b\_m\\}$ be a set of buckets, with $m \leq n$. Let $T(b\_j)$ represent the total weight present in bucket $b\_j$, which is the sum of all the weights present in $b\_j$.
>
> What is the optimal way to distribute all the weights $w\_i$ into the buckets $b\_j$ to minimize the metric $\max T(b\_j) - \min T(b\_k)$ for some $j,k \leq n$?

I know that this seems to be a variant of the bin packing problem and I have found some heuristics such as the ones described here.

But is this problem really equivalent to the one in the link? My problem does not have an upper limit on the capacity of each bucket, which makes it quite different from the routine bin-packing problem.

If anyone has an optimal solution and if it's NP-hard, an approximation algorithm, I'd love to hear it.

# Answer
It seems that this is exactly the $k$-partition problem, which is NP-hard even in the $k=3$ case.

There are decent approximation algorithms, though:

* Greedy provides a $\tfrac{4}{3} - \tfrac{1}{3k}$-approximation (a PTAS).
* FPTAS exist.
> 2 votes

---
Tags: algorithms, approximation, knapsack-problems
---


title: Is every problem in NP solvable?

text:
# Question
Title: Is every problem in NP solvable?
Is every $\sf NP$-problem solvable or are there problems that have no working algorithm to solve but have algorithms to verify?

# Answer
> 6 votes
Working from the "machine" definition (that a problem is in $\mathcal{NP}$ if and only if it can be decided by a *non-deterministic* Turing Machine in polynomial time), we can take a similar approach as in Bill Province's verifier based answer.

Given a problem $P \in \mathcal{NP}$, there is, by definition, a non-deterministic Turing Machine $M\_{P}$ that correctly decides whether $x \in P$ or not in time bounded by $|x|^{c}$ for every $x \in \Sigma^{\ast}$ and some fixed $c \in \mathbb{N}$.

The gap between this and a "working" algorithm is the non-deterministic steps that $M\_{P}$ makes during the computation. For each non-deterministic step, there is a finite number of choices that $M\_{P}$ can possible make (even sticking rigidly to Turing Machines, there are at most $k=|\Gamma\times\Sigma\times Q\times \\{L,R\\}|$ possible transitions from the current state).

We can then simulate the non-determinism by branching on each of these possibilities or exploring each in turn. Given that $M\_{P}$ performs $O(|x|^{c})$ steps, even if every single step were non-deterministic, the number of steps in this exhaustive search of the possibilities would be $O(k^{|x|^{c}})$ - unpleasantly large, but certainly finite.

# Answer
> 3 votes
Every problem in $\sf NP$ is decidable (solvable). Just try out all possible "witnesses" for the verification algorithm. This can be understood as a brute force algorithm over the witnesses.

There is one caveat, though. You have to know the maximal length of the witness encodings you have to try out. Since the problem is in $\sf NP$ you know that there exists some $k\>0$ such that it suffices to consider encodings of length $O(n^k)$, for $n$ being the length of your input. You can now set up a brute force algorithm for each $k\in \mathbf{N}$.

As pointed out in the comments, you might also want to go over all constants $c$ hidden in the big-O notation. However, since you test *all* $k$, you will find a $k'\>k$ such that $n^{k'}$ dominates $cn^k$ for all constants $c$.

Under these algorithms there *exists* one (in fact infinitely many) algorithm that decides the problem. So the sketch of the proof I gave you is not constructive unless you know the $k$.

# Answer
> 2 votes
The short answer is that if a problem is in NP, it is indeed solvable.

A language L in NP, by definition allows for the existence of a "witness" machine M such that the following is true: There is a polynomial p(n) such that if S is in L then there is a certificate C such that M(S, C) accepts in an amount of time bounded above by p(length(S)). Without loss of generality, we can assume that C is expected to be just a string of 1s and 0s.

Therefore, if we know that a language L is in NP, we know that such a witness machine M exists with the provided polynomial. We might not have a means of finding M or its polynomial, but we know that such a machine exists. So theoretically, using M, we can decide L for a given input S: just consider all possible certificates with length less than or equal to p(length(S)) with the given machine. For a given S, the number of strings is finite, and therefore decidable.

---
Tags: complexity-theory, computability, undecidability, decision-problem, np
---


title: Extended knapsack: is it NP-complete?

text:
# Question
Title: Extended knapsack: is it NP-complete?
I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same:

Maximize the value of

($\sum\_{i=1}^n v\_i \cdot x\_i) + B \cdot \frac{W}{r}$

subject to

$ \sum\_{i=1}^n w\_i \cdot x\_i \leq W$.

Here, $W$ and $B$ are constants, and $r$ is an integer variable with $1 \leq r \leq n$, whose behavior vis-à-vis the variables $v\_i$ and $w\_i$ is unknown to me.

It is obvious that if $B$ is 0, this reduces to the classical knapsack and is hence NP-complete, but is it still NP-complete otherwise? Can we say anything about this problem considering possible behaviors of $r$?

It's been a while since I studied algorithms; please bear with me if this looks too simple (let me clarify that this question arose from research; I'm not a kid trying to cheat on homework). I have also not found an answer in the responses to other knapsack questions asked on this forum.

# Answer
> 2 votes
$B\*\frac{W}{r}$ is a constant, so adding it to your objective function has no effect on the solution. The problem is NP-complete, regardless of the values of $B$ and $r$.

---
Tags: complexity-theory, np-hard, knapsack-problems
---


# Question
Title: Natural Language Parser that can handle syntactic and lexical errors
I have some background in natural language processing and I know that all parsers (top down or bottom up, or mix), at least when I studied just about a few years ago, cannot handle any error. A small error like a grammatical one or a spelling one will result in unexpected parsed tree.

This is unacceptable in natural language in most cases. Thus I have been trying to find a way to make a new one with a different approach.

The basic general abstract idea is that I will use a top down dynamic programming approach. Given a string of text with $n$ tokens, several top down fillers will be generated. These fillers will look at the tokens to see if they can find and fill constituents that they are missing. Because of this, these fillers might leave gap after they have found everything they need. This is supposed to make the parser more robust.

An example will be best to illustrate this idea:

Given the sentence: `I saw the ordinary thing`.

One top down filler can be. $S \rightarrow Subj - Verb - Object$. This filler will try to look for span that it can use to fill its expectation of seeing a $Subject$ followed by $Verb$ and $Object$. This means it will deployed three other fillers in sequence. The first one is $Subj$. This filler will scan and add to the cache three possible subjects which are $I$, $saw$, $thing$. $I$ is put in span $\[1,1\]$, $Saw$ in span $\[2,2\]$, $thing$ in span $\[5,5\]$. This will result in a total of three potential pending parse trees. Then with each of these pending parse tree, $Verb$ filler is deployed to scan the span after each possible subject. $Object$ filler is deployed to scan the rest.

With the above approach, sentences such as `I .. eh... saw the big thing` or similar constructs do not cause problem because fillers look for what they need and fill them into the tree. This problem is dealt with when all fillers have completed. Fillers that leave lot of gaps (unused tokens) will not generate parses having high score compared to parses generated by fillers that use up all tokens.

This is also my approach to deal with subject-verb agreement and male-female as well as singular-plural agreement. You deal with them at the ranking stage so that you can give your parser much better error tolerance. Sentences such as `Maybee they ehh can get something` can still be parsed. One resulting parse will just not use `Maybee`. The top parses will then be used again, this time to look for unused tokens. Unused tokens will be processed with spelling correction, did-you-mean style. One can see how it works with incorrect sentences like `This is a valide argument`. Even incorrect sentences like `They did got it` are still parsed ok.

There will be other fillers which cannot find all they need such as conditional sentence filler. $CondS \rightarrow "If" - S - \["then"\] - S$. Some filler such as imperative $ImpS \rightarrow \["Please"\] - Verb - Object$ will complete most of the times because it can find all it needs abeit leaving gaps, but then it is a ranking problem to make sure that the correct one is returned.

**So my Question** is:

* Has anyone ever thought of this approach? Any reference papers?
* If nobody used it before what may be the potential problem?

# Answer
> 2 votes
I assume you already know about dynamic programming parsing, aka chart parsing. This is usually defined for Context-Free grammars (CFG), but can be extended to other grammatical formalisms, where it can make more or less sense, depending on the structural complexity of these algorithms. There are various papers describing chart parsing for specific formalisms, particularly in the computational linguistic literature. One general view of the underlying structure common to all these algorithms is described in a 1995 paper by Lang, and to be found in the Grune-Jacobs book, relies on a very simple view of parsing as an intersection of two languages: the first is the singleton regular language containing the sentence $w$ to be parsed, and the second being the language $L$ for which we are given a grammar $G$. The idea is that a single sentence $w$ can always be read as a FSA (or a regular grammar) as in the following example for the sentence $abac$ $$q\_0 \stackrel{a}\longrightarrow q\_1 \stackrel{b}\longrightarrow q\_2 \stackrel{a}\longrightarrow q\_3 \stackrel{c}\longrightarrow q\_f$$

Using this FSA $A\_w$ and the grammar $G$ of the language $L$ (assume first $L$ to be a CF language, and $G$ a CFG), the old cross-product construction due to Bar-Hillel, Perles and Shamir (1961) to prove closure of CFL with regulr sets can be used with $A\_w$ and $G$, and yield a new CF grammar $G\_w$, which naturally generates only $w$ when $w\in L$, or the empty language $\emptyset$ when $w\notin L$. The important point is that, when $w\in L$, the grammar $G\_w$ generates $w$ with exactly the same parse trees as the original grammar $G$, up to a renaming of non-terminal, though the correspondence between non-terminals is kept (let us ignore details). In other words, we just described a parser that yield a parse forest $G\_w$ from which all the parse trees for $w$ can be extracted, simply by using the grammar $G\_w$ as a generator.

As it turns out, the dynamic programming chart parsers are just optimized variants of this very basic construction called *parsing as intersection*.

The nice point about it is that it lends itself to many variations. Closure under intersection with regular languages is a very common property, so that this is a guide for producing parsers for a great variety of formalisms, though it makes effective sense only for those that have a simple generating structure (loosely). Typically it works very well for tree adjoining grammars (TAG) an other mildly context sensitive languages.

Another point is that, rather than parse only strings, one can parse complete regular sets, keeping only the sentences that are also in the context-free language. And it is largely compatibles with the many "optimization" techniques commonly found in chart parsing

This is very important in natural language processing (NLP), and particularly in speech processing, since the result of the first pass of speech processor to identify the spoken words is usually not a single string of words, but what is usually called a word lattice (see Ambiguity and sharing in Natural Language Parsing, which is actually the title of an answer to a question).

The interesting point is that a word lattice (see diagram in previous reference) may be seen as a FSA that recognizes all the candidate sentences (after noise processing) that could be the sentence to be parsed. But chart parsing can be applied as well, as can the intersection construction.

Now, it may well be that the word lattice contains spurious words to be eliminated, or completely garbled sequences corresponding to arbitrary number of missing words, or misunderstood words. That can be modeled as a General Sequential Mapping (GSM) that does some editing on the input sentence, adding, removing or substituting words, possibly in a (finite) contextual way. Both regular and context free languages are preserved by GSM mapping. Typically, the editing GSM can be applied to the word lattice, yielding a new regual language and its FSA (possibly even with cycles). Then the parsing process is applied to that new FSA. This part is, I think, what you mainly wanted to describe in the question.

The next point is that not all proposed sentences, or not all corrections have the same likelyhood. Actually, word lattices may be weighted structures that give weights to the corresponding sentences in proportion to some likelyhood they they are correct.

Then the editing GSM can also have weighted transition corresponding to some standard likelyhood that such error may have occurred.

Finally, the (CF) grammar of the language itself may be weighted.

The dynamic programming construction can use these weight (possibly probabilities) to determine what are the most likely parses of the given input according to the grammar used.

Note that I have been skipping the morphological analysis that recognizes words, and uses similar techniques to end up with the word lattice.

I am also skipping the use of attributes or feature structures, that can combine with the process, provided they meet some algebraic constraints.

The algebraic constraints (that concern also the numerical weights) are related to the algebraic structures of the grammars themselves. Typically, a CF derivation backbone (that is more than CF languages) relies on semiring structures.

A CF rule such as $X\to VXW | aV$ may be read as an equation of the form $X = V\cdot X\cdot W \cup \\{a\\}\cdot W$ where the wariables take their values in sets of sentences (i.e. in languages). The domain of languages is a semi-ring under the two operations: Union "$\cup$" and concatenation "$\cdot$". And a context-free grammar is a specific kind of equation in that domain.

You should find more on this use of semirings in Goodman's "Parsing Inside-Out 1998.

There are some other references in my answer to the question "Is there a favoured data structure for storing ambiguous parse trees in Natural Language Processing?"

---
Tags: reference-request, natural-language-processing
---


# Question
Title: What is different between "Arithmetic Calculation" and "Calculation" in computer science?
What is different when you say "Arithmetic Calculation" and "Calculation" in the context of the computer science?

The "arithmetic" in the former seems needless to me since all calculations are arithmetic.

Is there some meaning that is enhanced by adding "arithmetic" in this case?

Thank you in advance.

# Answer
> 2 votes
"Arithmetic calculations" are those involving addition, subtraction, multiplication and division of numbers. eg (2+13)/5

There are also "algebraic calculations" eg Find y such that y + 2x = 13 and more.

# Answer
> 1 votes
I'm sure my word processing program must do calculations, but since neither my input nor the results are expressed in numeric form, it hardly seems like arithmetic calculation. Is there an arithmetical operation called Insert, delete, or italicize? Of course, you could say these operations are reduced to arithmetical calculations, but in actuality, all calculations on a digital computer consist of combinations of and/or and nand/nor logic operations, some of which simulate arithmetic.

# Answer
> 0 votes
What the computer does is move electric charges around, change magnetic state in some supports, read magnetic states, change some of this into light pulses for transmission, and many others similar microphysical manipulation.

Now it is up to you to interpret all that in whatever way you find convenient, and give it a name accordingly.

Ignoring the physics, and going up one level, you manipulate bits. A bit is just something that can have one of two possible states. All that matters is that you can distinguish them. You may call them 0 and 1, or true and false, or Yin and Yan, or black and red, or up and right.

Then there ways of manipulating them that encode more complex things. You can interpret a sequence of bits as a number, or as a letter, or as a fragment of a text, or as a painting, or as a symphony. Your choice, with appropriate encoding.

Then are you doing Arithmetic calculations, or composing music, orwriting/reading a novel, or solving an equation ...? It depends on the encoding and the manipulation.

But it is always calculation, in a sense, Calculation comes from the latin calculus : stone, as stones were initially used for counting (which is indeed arithmetic). But what survived is the idea of manipulating stones. And the name calculus is generally used to indicate some form of manipulation of entities supposed to represent something, usually the manipulation of symbol in the modern world.

So, yes, the computer does calculations. But that only means it is pushing bits around. And it may be for any purpose, since it is a universal way of representing information.

Note: The use of the word calculus alone to mean also diffential and integral calculus is more a linguistic accident. See: What are the justifications and historical reasons regarding the choice between the words 'calculus' and 'algebra'?

---
Tags: terminology, arithmetic
---


# Question
Title: Stable marriage problem with more people then priorizations
I am trying to solve a stable marriage problem where I have e.g. 20 women and 20 men, but they always only prioritise 4 pre-selected people of the opposite sex.

1. My algorithm distributes all men and women, so that everybody has 4 potential partners. This happens through the whole group of 20 (not in groups of 4 x 4, which would easily work). If man A has woman B in his list then he is also in her list.
2. The people prioritise their potential partners from 1 to 4.
3. My algorithm tries to find the optimal partner depending on their priorization.

This means that they marriage has to be with one of the 4 potential partners. The order of their prioritisation decides on the order the proposing and accepting matrix is gone through, similar to this animation shown in wikpedia.

So basically I have 20 rows of each proposers and acceptors, but only 4 columns.

So far I always get an almost stable solution, in which in the end only one man and one woman can not marry.

How could I solve this problem for even bigger numbers of people (rows), but always keeping 4 (or between 3 and 5) prioritisation (columns)?

# Answer
> 3 votes
In general, you won't be able to marry all but one of the men and all but one of the women. For example, suppose that all of the men want to marry the same four women: you'll get exactly four marriages and an arbitrarily large number of bachelors and spinsters.

---
Tags: algorithms, matching
---


title: Diophantine equations and P=NP

text:
# Question
Title: Diophantine equations and P=NP
It was proven that the problem of determining whether a given Diophantine equation has a solution is undecidable (and therefore has no polynomial time algorithm). But we can check proof certificates (that is, solutions to the equation) in linear time by plugging in our solution and evaluating. So the problem is in NP. Why does this not imply P $\neq$ NP?

# Answer
> 7 votes
Every problem in **NP** is decidable. Since determining whether Diophantine equations have solutions is undecidable, it cannot be in **NP**. Therefore, although the solution to the equation is a certificate, the size of this certificate is not bounded by any polynomial in the size of the input.

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


# Question
Title: Constructing a deterministic one way infinite single tape Turing machine
If I have an input string that is only composed of $a$'s and $b$'s, how can I construct a Turing machine that only accepts strings where the number of $b$'s divides the number of $a$'s?

For example:

$aaaabb$ is accepted

$baaab$ is rejected

# Answer
> 1 votes
Here is a rather reasonable way to implement this in Turing machines:

1. Sort the `b`s and the `a`s so that the input tape is composed of `b`s followed by `a`s.
2. Repeatedly perform the following operation: remove $B$ `a`s from the end of the input tape, where $B$ is the number of `b`s.
3. Accept if you never got stuck perform an iteration of the previous step.

The second step can be implemented without explicitly counting $B$. For the first step, you can implement the simplest algorithm you can think of, say bubble sort.

---
Tags: turing-machines
---


# Question
Title: Multiplication of two or more algebraic quantities
Recently, I was facing the problem how to multiply to two or more algebraic quantities in c++. For example, if the two algebraic quantities are

$$x^2-2x+3, \text{and } x-5$$

then the result of multiplication will be

$$x^3-7x^2+13x-15.$$

My question is that how to read the two algebraic quantities, find out the result of multiplication and print the result in c++. I need hints and is there something to learn to multiply the two or more algebraic quantities by programming. If so,what is that?

# Answer
> 4 votes
Your *algebraic quantities* are **polynomials in one variable**. Multiplying two polynomials is an important computational problem with many applications. You can store a polynomial in two ways:

* store the coefficients, that is for $p(x)=3x^2-x+3$ you store $(3,-1,3)$
* store enough samples, that is for $p(x)=3x^2-x+3$ you might store three values like $p(0)=3,p(1)=5,p(-1)=7$ (if your highest exponent is $k$ you need $k+1$ samples)

To multiply two polynomials you can do the following. Assume the coefficients of the first polynomial $A(x)$ are named $a\_i$ and of the second $B(x)$ they are named $b\_i$, then the coefficients for $A(x)B(x)$ are the coefficients $c\_i$ with $$c\_k= \sum\_{(i,j)\colon i+j=k} a\_ib\_j$$

Without tricks this takes $O(n^2)$ time.

Another possibility is to multiply the samples (if they are taken at the same positions). The problem here is, that the product has a higher degree. That means that you need more samples than you needed for the original polynomials. So you had to record more samples in the beginning. What is even more severe is that it is not easy to evaluate the polynomials on arbitrary positions if you only have the samples. So the multiplacation goes fast in $O(n)$ time if you have enough samples, but the evaluation might need $O(n^2)$ time per se.

But here is the thing. You can change from one representation to the other in only $O(n \log n)$ by a famous algorithm called **fast Fourier transform (FFT)**. In a nutshell you pick you sample points very clever and then you *divide and conquer*. Using FFT you can multiply and evaluate polynomials in time $O(n\log n)$. If you dont care so much about speed, just use the coefficient representation and the formula above.

---
Tags: algorithms, computer-algebra, polynomials
---


# Question
Title: Count all possible unions in a collection of sets
Say we have a collections of sets $\mathcal X = \\{X\_1, \dots, X\_n\\}$ (not necessarily disjoint), and we want to count the number of possible unions of sets in $\mathcal X$, i.e. the size of $\\{\bigcup\_{Y \in \mathcal Y} Y \\,|\\, \mathcal Y \subseteq \mathcal X \\}$.

Is there a name for this problem? What are the fastest algorithms to solve this problem?

# Answer
> 4 votes
I found the answer here. It is called the union closure and the complexity appears to be the same as computing the number of maximal independent sets in a bipartite graph.

---
Tags: combinatorics, sets
---


# Question
Title: How do I interpret a binary tree generated using Huffman coding algorithm?
In the lecture note here, a binary tree was generated from the huffman algorithm. However it did not explain what this graph mean.

From this binary tree, what can we say about the encoding for the alpha bets a, c, b, f, e, d?

# Answer
> 1 votes
The encoding of a particular character is the sequence of 0's and 1's you encounter on the path from the root to that character.

---
Tags: binary-trees, encoding-scheme
---


# Question
Title: Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)
Suppose I have $M=\\{1,\ldots, n\\}$ men and $W = \\{1, \ldots, n\\}$ women and $B =\\{1, \ldots, m\\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a marriage can be set up among the corresponding man and women.

Each broker $i$ can set up a maximum of $b\_i$ marriages and a person can only be married once. Also we assume all marriages are heterosexual.

I want to determine the maximum number of marriages possible and I want to show that the answer can be found be solving a **maximum-flow problem**.

What I've tried:

Make source and sink nodes with opposite demand. And then for each ordered pair $(i,j)$ where $i$ is a woman and $j$ is a man making a node. For each broker $j$ make a corresponding node and introduce an arc with capcity $b\_j$. For each node $(i,j)$ make an arc from broker $k$ with capacity $1$ if broker $k$ can arrange a marriage otherwise $0$.

However, after this I stop. I need to keep track of state, that is no person gets married twice !

# Answer
> 1 votes
You shouldn't need to keep track of state. This can all be handled with capacity constraints over the nodes. The network can be structured as follows:

Start with the graph where one partition consists only of the "men" nodes and the other partition consists of the "women" nodes. Now, add a node for each broker $b$ and for each marriage pair $(m, w)$ on $b$'s list create two edges $(m, b)$ and $(b, w)$. Finally add a source node connected to all men and a sink node connected to all women (you can add another arc between those to simplify constraint cases if you want, but it's not necessary).

So now we have a graph, but to have a proper flow-network we need capacity constraints. For each man and women node we have a capacity constraint of 1, since they can each only marry at most one person. For the $i$th broker node, add a capacity constraint of $b\_i$. This way the total number of flows (marriages) going through the broker is at most $b\_i$.

Compute maximum flow over this graph and you should be good to go.

---
Tags: graphs, reductions, optimization, network-flow
---


# Question
Title: Complexity of natural language processing problems
Which natural language processing problems are NP-Complete or NP-Hard?

I've searched the and tags (and related complexity tags), but have not turned up any results.

None of the NLP questions that are recommended are helpful, the closest are the following:

The Wikipedia list of NP-complete problems does not list any complexity results for NLP.

The only lead I've found is the paper *Theoretical and Effective Complexity in Natural Language Processing* by J. Morin (1995).

Any help or pointers is appreciated!

# Answer
LFG (Lexical-Functional Grammar) recognition is NP-Complete.

Edit per request: Lexical-Functional Grammar (LFG) \[1\] is a theory of natural language syntax, developed as an alternative to Chomsky's theories of transformational syntax. Some versions of Chomsky's theories are computationally equivalent to Unrestricted Grammars. LFG by contrast provides a grammar formalism which consists of a context-free grammar augmented by a feature system.

It's the feature system that's NP-complete. The proof works basically by noticing first that the feature system is at least as powerful as propositional logic, and second that grammaticality rests on satisfying all the propositional constraints governing the sentence. So it's the Satisfiability Problem hiding under another guise.

\[1\] "Lexical-Functional Grammar: A Formal System for Grammatical Representation" by Ronald M Kaplan and Joan Bresnan. The paper originally appeared in *The Mental Representation of Grammatical Relations*, ed. Joan Bresnan (Cambridge, MA: The MIT Press, 1982).
> 2 votes

# Answer
Maybe one should first define what is a natural language processing (NLP) problem.

For example, Context-Free (CF) grammars and languages were introduced by linguists (Chomsky type 2 language, work of Bar-Hillel and others). Ambiguity is a major problem in Linguistics for real sentence analysis, and in the formal study of CF grammars (ambiguity) and languages (inherent ambiguity). Ambiguity of a grammar is only semi-decidable.

So I guess the problem of ambiguity should be an answer to your question. Does it classify as a NLP problem?

Now if you take some modern formalizations of syntax, such as a CF backbone with feature structures (i.e. structured attributes), you quickly get Turing power (cf LFG which have been proved NP hard, or even Turing complete, depending on variants). So , if you are not careful, you have all the complexity problems you might dream about.

For more, you can also look at this question from SE-Linguistics: "Does the P versus NP conjecture in computer science have any direct relevance to linguistics?"

In my own answer, I actually criticize the meaningfulness of the question, or at least of some of its interpretations. Many of the problems that are considered in linguistics, regarding analysis of sentences, for translation or other purposes, are small problem, to be solved in a very short time. Some linguists might even dispute that there is real recursion in language structure, since whatever recursion there is is rarely very deep. Hence one might wonder about the linguistic relevance of complexity analysis which is defined asymptotically. The first question should be whether we ever get close enough to the asymptote for asymptotic analysis to be meaningful.

However, this remark does not apply to some aspect of NLP, when massive amount of data have to be processed. I know of at least two cases:

* data mining in large corpora.
* the inverse problem of linguistics: analysis of large corpora to mechanically extract the data characterizing a language, both structurally and to produce extensive lists of constituents, such as phonemes, vocabulary for various parts of speech (aka preterminals), prefixes and suffixes, or inflection mechanisms, to give a few examples.

I am no expert in data mining, and thus do not know whether it actually raises complexity problems related to the size of the corpora being processed. In that case, asymptotic complexity would indeed be an issue. But if it is mostly composed of a large number of small additive tasks, then it is more doubtful that asymptotic complexity matters much. However, I would imagine that some data mining techniques will work with correlations between independent documents, and that should raise corpus dependent complexity issues.

In the case of the inverse problem of linguistics, the identification of a language (which, I guess, could be considered a data mining problem), we are indeed trying to extract information by correlating all parts of large corpora. Then asymptotic complexity becomes extremely relevant. I have unfortunately no specific problem in mind, probably because such systems have a pragmatic aim, and people developing them will tend to simply avoid any form of higher complexity, quadratic being probably already beyond the available resources. But a search of the literature would probably raise some complexity issues.

Another point is that linguistics does not have clearcut laws like physics. It is more a matter of being close enough to what might be considered current linguistic consensus, since no two people speak exactly the same language. Hence, good approximations are usually sufficient when the aim is so elusive. The techniques I have seen were mainly fix-point techniques to identify parameters by iterative recomputation of some function based on the corpus structure, until it no longer makes much difference (plus user input to weed out remaining pathological cases).

Analysing properties of grammars and other formalized linguistic structures may also be a source of high complexity problems, as mentioned above for ambiguity, since natural language descriptions are usually large enough for asymptotic analysis to be meaningful.
> 4 votes

# Answer
as in my comment, sometimes P/NP complexity while quite powerful can be a hammer that makes all complexity questions look like nails, and in the field of AI & language translation with statistical, probabilistic, imprecision, and machine learning aspects, it may not be the ideal measurement at times, and theoretical computational complexity is not always considered central or relevant esp in more applied AI/ machine learning. in some ways the entire field has a more empirical aspect to measuring applied problem complexity. however, here is one angle not yet pointed out in other answers, there are some P/NP considerations in NLP language translation. eg these two papers
> 1 votes

---
Tags: complexity-theory, reference-request, np-complete, np-hard, natural-language-processing
---


title: Second order function formalization

text:
# Question
Title: Second order function formalization
I need to work on a optimizer for a language whose operator are second order functions.

They are the well known ones filter, map, reduce, fold, foreach etc. etc.

I need to formalize as much as possible the language. I mean I would like to have at the end a description such this:

"Filter is function from this domain to that codomain, it has this and that properties, under some condition also this property holds"

Can you suggest me some publication/book where this work has been (at least partially) done?

# Answer
You may not be able to completely specify formally in a tractable way the semantics of your functions, depending on what they are. But doing some of the work, even incompletely may help you significantly with optimizing your programs, since it may be enough to establish whatever properties are needed for optimization.

The first thing you want to do is to type your functions. For this, you probably want some kind of polymorphic typing (see ML or CAML), using type variables, as some of the base types you operate on will be left open.

Most of these function take several arguments, and (following the discussion in comments with @Jake) you may want to consider what would be a convenient order, and more to the point, whether you want them curried (or currified) or not.

For example, if we note `[a]` the type for a list of elements of type `a`, then you can define the function `map` as:

* a function of two arguments, the first being a function from `a` to `b`, and the second a list in `[a`\], and returning a list in `[b]`, i.e.
`map: (a→b)×[a] →[b]`
* a function of one argument which is a function from `a` to `b`, and returns a specialized mapping function that maps lists in `[a`\] to lists in `[b]`, as specified by the argument to `map`, i.e.
`map: (a→b) →([a]→[b])`

The latter is a curried version of the former. They give you the same computing power, but the curried one may be more convenient for optimization (just my intuition) as it decomposes structures.

Then the kind of information that you may need may depend on the kind of optimizations you intend to implement. Many types of optimizations ("strength reduction" is a typical example) may require knowing algebraic properties of your functions. But that may also depend on the algebraic properties of the types or type constructors used, such as the existence of "identity element" with respect to some operations (such as the empty list). I doubt your specification/formalization problem can be restricted to just your second order functions.

Typically, a relation such as:

`head (map (f,l))= f(head(l))` may be very useful for some optimizations.

or more trivially:

`map(f,[]) = []` where `[]` denote the empty list.

I do not recall all the literature on these issues. But you may want to look at abstract data types, formal algebras, and the algebraic techniques used in optimization.

There are probably other properties, less algebraic, that you may be interested in defining and using.

An important aspect is also whether your function are purely functional, or whether they have side effects. A map function could possibly destroy the list given as argument, the result reusing the same memory locations.
> 2 votes

# Answer
You may want to have a look at the Coq proof assistant. Its type system allows to express types as in other functional languages (e.g. `filter` is a function from `[A]` to `[A]`) and much more. You can easily add arbitrary properties.

Here is the definition of `filter`, taken from the list module of the standard library:

```
Fixpoint filter (l:list A) : list A :=
  match l with
    | nil => nil
    | x :: l => if f x then x::(filter l) else filter l
  end.

Lemma filter_In : forall x l, In x (filter l) <-> In x l /\ f x = true.

```

The first part is a usual definition of `filter`, but the last line expresses more interesting features about it.
> 2 votes

---
Tags: programming-languages, functional-programming, formal-methods, program-optimization, abstract-data-types
---


# Question
Title: MIPS with one read port in the register file?
I'm studying the MIPS multi-cycle datapath, and I'm wondering what would happen if there was only one read port in the register file for certain instructions.

First, for R-type instructions, I know that it takes in 2 registers(for example, with 'add', rs and rt are both passed into read-port 1 and read-port 2 in the register file) and then added in the ALU. With only one read-port, the fetch step will be the same amount of time (fetching the instruction won't be affected), but the execution step will take 2 clock cycles instead of 1, because there will be a clock cycle for each time a register is passed in. Then, the other steps will also take the same amount of time after that.

But what about the load and store instructions? The register file takes rs and rt into the read-ports normally, but for example, sw STORES it's value in rt. Will this mean that the execution step won't be affected because rt will be passed into the "write register" port? Could anyone clear this up for me?

# Answer
> 3 votes
For your MIPS CPU with 1read + 1write register file :

* ALU instructions will last two cycles as you describe.
* Load instructions can be executed in 1 cycle (with data in cache, etc...)
* Store instructions must be split in two cycles to get the two source registers.

Another example, in SPARCs, STORE R1,\[R2+R3\] require two cycles with a 2R1W register bank, whereas LOAD \[R1+R2\],R3 can be executed in 1 cycle.

---
Tags: computer-architecture
---


# Question
Title: What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph?
Say I have an undirected finite sparse graph, and need to be able to run the following queries efficiently:

* $IsConnected(N\_1, N\_2)$ - returns $T$ if there is a path between $N\_1$ and $N\_2$, otherwise $F$
* $ConnectedNodes(N)$ - returns the set of nodes which are reachable from $N$

This is easily done by pre-computing the connected components of the graph. Both queries can run in $O(1)$ time.

If I also need to be able to add edges arbitrarily - $AddEdge(N\_1, N\_2)$ - then I can store the components in a disjoint-set data structure. Whenever an edge is added, if it connects two nodes in different components, I would merge those components. This adds $O(1)$ cost to $AddEdge$ and $O(InverseAckermann(|Nodes|))$ cost to $IsConnected$ and $ConnectedNodes$ (which might as well be $O(1)$).

If I also need to be able to remove edges arbitrarily, what is the best data structure to handle this situation? Is one known? To summarize, it should support the following operations efficiently:

* $IsConnected(N\_1, N\_2)$ - returns $T$ if there is a path between $N\_1$ and $N\_2$, otherwise $F$.
* $ConnectedNodes(N)$ - returns the set of nodes which are reachable from $N$.
* $AddEdge(N\_1, N\_2)$ - adds an edge between two nodes. Note that $N\_1$, $N\_2$ or both might not have existed before.
* $RemoveEdge(N\_1, N\_2)$ - removes an existing edge between two nodes.

(I am interested in this from the perspective of game development - this problem seems to occur in quite a few situations. Maybe the player can build power lines and we need to know whether a generator is connected to a building. Maybe the player can lock and unlock doors, and we need to know whether an enemy can reach the player. But it's a very general problem, so I've phrased it as such)

# Answer
This problem is known as *dynamic connectivity* and it is an active area of research in the theoretical computer science community. Still some important problems are still open here.

To get the terminology clear, you ask for **fully-dynamic connectivity** since you want to add and delete edges. There is a result of Holm, de Lichtenberg and Thorup (J.ACM 2001) that achieves $O(\log^2 n)$ update time and $O(\log n / \log\log n)$ query time. From my understanding it seems to be implementable. Simply speaking the data structure maintains a hierarchy of spanning trees - and dynamic connectivity in trees is easier to cover. I can recommend Erik D. Demaine's notes for a good explanation see here for a video. Erik's note also contain pointers to other relevant results. As a note: all these results are theoretical results.

These data structures might not provide *ConnectedNodes* queries per se, but its easy to achieve this. Just maintain as an additional data structure the graph (say as doubly connected edge list) and the do the depth-first-search to get the nodes that can be reached from a certain node.
> 11 votes

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


# Question
Title: Blob detection as Constraint satisfaction problem?
In image processing I have a black and white image which is represented by matrix {0,1}, I have to find blob (a region of connected pixels) in it. I'm confused, can this problem be reduced to Constraint Satisfaction problem (as p/np complete)?

Black and white image with white blobs.

# Answer
> 4 votes
The constraint satisfaction problem (CSP) is **NP**-complete. Identifying blobs is a question about graph connectivity which is in **P**. Therefore, yes, the question you're asking reduces *to* CSP but this doesn't tell you anything useful: it just says that CSP is at least as hard as this problem but it might be harder. (In fact, it is strictly harder if **P**$\neq$**NP**.) Since your problem is in **P**, it is not (believed to be) **NP**-complete.

A related question is whether the problem can be expressed directly as a CSP without needing a reduction.

If a blob is any connected region then, in particular, any blob contains two adjacent pixels and any two adjacent pixels are part of a blob. Therefore, if all you want to know is whether an image contains at least one blob, this is a constraint satisfaction problem.

However, if you want to identify a whole blob (e.g., output a list of all the pixels within some blob) or identify or count all the blobs, the problem is no longer a CSP. The reason for this is that CSPs are not able to express connectivity conditions: there is no CSP in a finite constraint language that says "This graph is connected" because every instance of CSP is equivalent to a first-order formula and first-order logic can't tell the difference between connected and disconnected graphs.

---
Tags: np-complete, image-processing, computer-vision, graphics, constraint-programming
---


# Question
Title: Implement a search procedure in terms of a set test procedure
Suppose you have a procedure $\mathrm{Prod}(S, t)$ that inputs a finite set of integers $S$ and an integer target $t$, and outputs either “yes” or “no” according to whether there exist distinct elements $x\_1, \dots, x\_n \in S$ with $\prod\_{i=1}^n x\_i = t$. You would like to implement an enhanced version of $\mathrm{Prod}(S, t)$, called $\mathrm{ProdSearch}(S, t)$ that outputs the elements $x\_1, \dots, x\_n$ if such elements exist.

Describe an efficient such procedure $\mathrm{ProdSearch}$ that works by making multiple calls to $\mathrm{Prod}$ as a sub-routine. Carefully explain why your procedure is correct.

# Answer
> 2 votes
Hint: Suppose you asked your oracle whether there is a subset of $\\{x\_2,\ldots,x\_n\\}$ whose product is $t$. What can you deduce if the answer is YES? What can you deduce if the answer is NO?

Here is the full solution:

> If the oracle answers YES, we deduce that we can remove $x\_1$ from $S$. If the oracle answers NO, we deduce that every solution must contain $x\_1$. We therefore remove $x\_1$ from $S$ and update our target product to $t/x\_1$. Continuing in this vein for $n-1$ more iterations, we find a solution. This requires at most $n$ calls to $\mathsf{Prod}$ in total.

# Answer
> 0 votes
I'm sorry, i'm going to solve this problem. But only this time, next time do it yourself:

Follow this procedure:

* call the function prod(s,t)
* if it says no, there is no such subset and you are done.
* if it says yes do this:

in pseudocode

```
var boolean = true;
array numbers // this is the set of your question
while(boolean)
{
boolean = false;
for(int i = 0;i<n;i++)
{
  var numbers2[numbers-1];//We are going to create an array(subset) with    all numbers less 1
  for(int j=i;j<numbers.size;j++)
  {
   if(i != j)
    numbers2[j] = numbers[i];
  }
  if(prod(numbers2,t) == "yes")
 {
   numbers = numbers2 //If it says yes then the number  on the set is not part of the subset we are looking for, we eliminate it
   boolean = true;//As we can keep eliminating numbers we are not over yet
  }

}
}

```

I hope is clear enough, this is prodsearch. As an aside, with aslightly modified version of this algorithm, you could solve an np-complete problem in polynomial time if you have sum instead of prod

---
Tags: algorithms, search-algorithms
---


# Question
Title: Substitution-based Operational Semantics of algebraic datatypes
Assume, I want to define the operational semantics for some subset of ML.

```
e ::= \\x. e | e e | c | match e with p+ | A e*
v ::= ... | \\x. e | ... | A v*
p ::= A p* -> e | x

```

Where *e* is the expression language, *v* are the values or normal forms, *p* are the patterns and *A* are the constructors for my algebraic datatypes.

Also assume I want to define the semantics based on substitution, not on environments. Finally, the language should be typable, e.g. every constructor will only be allowed to be applied to the same number of arguments.

So I assume, I have to introduce a "construct" operation and a "data declaration" and then substitute every constructor with an appropriate datatype declaration. But how does one define this "construct" operation? And how does the data declaration look like in an untyped calculus?

# Answer
> 2 votes
I found the solution to my answer: ADTs can be represented by a combination of sum-types and tuples enter link description here. In that representation, every construction takes exactly one argument (possibly the unit value).

Two special tagging forms, inl and inr for "inject left" and "inject right" are introduced. These forms allow the encoding of arbitrary tags. So every constructor is a one-argument function that applies the corresponding tag.

Hence, any data structure definition is operationally defined by the constructing operations:

```
data A | B | C

=>

let A = \\x. inl x in
let B = \\x. inr (inl x) in
let C = \\x. inr (inr x) in

```

The corresponding pattern can be substituted similarly.

---
Tags: functional-programming, semantics, operational-semantics
---


# Question
Title: Forward checking with conflict directed backjumping
Can somebody explain me how can I join forward checking with conflict directed backjumping in my CSP solver? I understand that when the consistency fails when I add a value to a variable, I should save all the instantiated variables of the restriction that fails, on the conflict set of the variable to which I gave a value. But what happens when there's no consistency failure but when I'm doing the inferences of the forward checking I found a contradiction? Do I need to know which restrictions failed and add the variables to the current variable conflict set?

My current approach:

My function that solves the CSP is recursive. So right now I'm doing the following, for each the current variable (the one I'm in the recursive step) I'm checking if the value that I give to her is consistent, if not, I add all the attributed variables of the restriction that fails to the conflict set of this variable. When I'm backjumping in the recursivity, I return this conflict set, and if any variable is contained in this set, it will try to change his value. (this implements the basic backjumping and with some other small changes I put my algorithm using conflict directed backjumping). I tested this part and it's working.

Now, when I add the forward checking, I need to get from the forward checking some informations when it finds contradictions (and this is the problem). Right now, I'm getting the variable where the contradiction occurs and all the attributed variables related to restrictions that failed.

Is this all the infromation I need from the backjumping?

# Answer
If forward checking detects that the potential assignment of a variable $x\_1$ leaves no valid assignments for the variable $x\_2$, one simple strategy is to just make the assignment to $x\_1$ and then queue $x\_2$ as the next variable to be assigned. When the assignment of $x\_2$ inevitably fails, your backjumping machinery will do what it always does and you need not code any special information gathering related to forward checking. In the meantime, you've saved all the time that would have been wasted doing (and undoing) a potentially exponential number of unrelated assignments that do nothing to resolve the inevitable conflict between $x\_1$ and $x\_2$.
> 3 votes

---
Tags: algorithms, artificial-intelligence, constraint-programming
---


# Question
Title: Haskell: implementation issues of some basic features
I'm taking a "Programming Language: Design and Implementation" course and our professor asked to make a case study about: Haskell programming language. In this case study he asks to make a report about: "implementation issues of some basic features. Can anybody list any good sources for this?

# Answer
The Wikipedia article cites a wide range of sources and has a decent "Further reading" section.
> 0 votes

---
Tags: programming-languages
---


# Question
Title: Big-O Notation of Anagram solution algorithm
In *Solution 1: Checking Off* of Problem Solving with Algorithms and Data Structures, just beneath the *ActiveCode: 1* extract (included at the bottom of this post for reference), it is stated:

> each of the n characters in s1 will cause an iteration through up to n characters in the list from s2.

...which to paraphrase (less succinctly), means "**each character** in s1 could result in **all characters** in s2 being inspected".

The following sentence states:

> Each of the n positions in the list will be visited once to match a character from s1.

Firstly I'm unsure which list is being referred, I think it means the variable `alist`, i.e. `s2`. Is this correct?

> The number of visits then becomes the sum of the integers from 1 to n.

Secondly (and the real point of this post), if each item in the list (variable `alist`) is inspected for each character in `s1`, then why is this not simply O(n) = n^2 as per "nested loops"? If n=5, then then sum(n) = 15, where as n^2 = 25.

I'm fine with simplifying the equation for summing 1 to n integers to get n^2, but I'm confused about how sum(5) = 15, whereas O(n) = n^2.

**ActiveCode: 1 Checking Off (active5)**

```
def anagramSolution1(s1,s2):
    alist = list(s2)

    pos1 = 0
    stillOK = True

    while pos1 < len(s1) and stillOK:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 = pos2 + 1

        if found:
            alist[pos2] = None
        else:
            stillOK = False

        pos1 = pos1 + 1

    return stillOK

print(anagramSolution1('abcd','dcba')

```

**Edit to add**

Having written this out it struck me that perhaps dropping the `(1/2)` and `(1/2)n` from the formula to `sum(n)` is the reason for the difference of actually summing `n`, as opposed to just doing `n^2`.

To be absolutely clear, I understand the formula for summing `n` is `n^2` when *dropping the non-dominant terms*. What I don't understand is why we're summing `n` and not immediately and directly stating it is actually `n^2` as a result of the nested loop and this sentence:

> each of the n characters in s1 will cause an iteration through up to n characters in the list from s2.

# Answer
Let's be concrete. Suppose `s1 = 'abcd'` and `s2 = 'dcba'`.

For the `a` in `s1`, it will take 4 iterations to find the `a` in `s2`. For the `b` in `s1`, it will take 3 iterations to find the `b` in `s2`. For the `c` in `s1`, it will take 2 iterations to find the `c` in `s2`. For the `d` in `s1`, it will take 1 iteration to find the `d` in `s2`.

So in this case, it does take `sum(i)` for `i = 1,...,n` iterations.

Now some quiet meditation should convince you than if `s2` is an anagram of `s1`, it will again take exactly the same number of iterations; the summands will just appear in a different order. (After all, whatever is the first character in `s2` will only require 1 iteration to be found, the second character requires 2 iterations, etc.)

If `s2` is not an anagram of `s1`, then the algorithm will short-circuit when the first character not in `s2` is tested. So then the algorithm will take less than O(n^2) time. But in the worst case, the algorithm takes O(n^2) time.
> 3 votes

---
Tags: complexity-theory, algorithm-analysis
---


# Question
Title: Implementing an interval tree using arrays?
Is it possible to create an interval tree using an array instead of the traditional pointer method? I know that for segment trees this is commonly done where the children of any element with index i are stored in 2i and 2i + 1 and the range is halved. For interval trees however, because the ranges added are not guaranteed to be halved each time, it seems like it might not be possible.

Could anyone prove or disprove whether interval trees can be implemented in this manner?

# Answer
> 2 votes
To a mathematician "prove or disprove" is a very strict requirement. I do not know how serious I should take this.

Every tree that has been implemented using pointers also has a array implementation. The trick is to do the addresses yourself as indexes to an array. That is usually called a cursor implementation.

Binary trees can be implemented, as you say, storing children of node $i$ at indices $2i$ and $2i+1$. This is sometimes called an implicit representation as no explicit structure is stored. The method is alwaus possible, but only advisable when the tree is perfect (all levels completely filled) or near perfect, like the complete trees used to store a binary heap. Otherwise it is a waste of space. When some node $i$ is missing in the tree then also nodes $2i$ and $2i+1$ are missing, and $4i,\dots, 4i+4$, etc.

---
Tags: data-structures, search-trees, arrays, intervals
---


# Question
Title: Decision problem which belongs to P reduced to a decision problem which belongs to NP?
Is it possible to have a decision problem $A$ which belongs to P and reduce it to a decision problem $B$ which belongs to NP, i.e. $A \leq\_{\mathrm{p}} B$, where $A$ belongs to P, $B$ belongs to NP?

# Answer
> 9 votes
Of course. Just take B=A, since every P problem is in NP.

# Answer
> 1 votes
Yes, of course you can

For instance:

We have 2-SAT( http://en.wikipedia.org/wiki/2-satisfiability ), that is an problem in P. We have CNFSAT( http://en.wikipedia.org/wiki/Boolean\_satisfiability\_problem ) which is an NP-complete problem. We can convert all 2-sat instances to cnfsat instances

If we have a 2-SAT formula like this:

$$ (x\_{1} \vee x\_{2}) \wedge (\neg x\_{3} \vee x\_{4}) $$

we can convert it to CNFSAT by inserting a dummy variable in each clause:

$$ (x\_{1} \vee x\_{2} \vee \neg x\_{5}) \wedge (\neg x\_{3} \vee x\_{4} \vee \neg x\_{6}) \wedge x\_{5} \wedge x\_{6} $$

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


# Question
Title: Can all decision problems reduce to undecidable?
If one could build a machine that for any input will never accept, but always loop forever, then will all problems reduce to this?

Or did I just misunderstood the idea of reduction?

# Answer
> a machine that for any input will never accept, but always loop forever

isn't a decision problem, and so it doesn't make sense to say it's undecidable.

However, given an undecidable problem $A$, there are always "more undecidable" problems $B$, i.e. those which would be undecidable even given an oracle for $A$. For example, the halting problem for Turing machines extended with an oracle for $A$.
> 3 votes

# Answer
The idea of reduction for a decision problem, is to prove that a NP-Complete problem is at least solvable in terms of another NP problem. As in, we break down (reduce) a problem to show that it may be solved.

Not all problems can be reduced to to be undecidable, only those that are not solvable in polynomial time such as NP-Hard problems.
> -4 votes

---
Tags: decision-problem
---


# Question
Title: Proof of equivalence of regular expressions (0 + 1)(0 + 1)* and (0 + 1)*(0 + 1)
How would I prove that the regular expressions RS and SR where R = (0 + 1) and S = (0 + 1)\* are equivalent? The '+' sign represents union of two regular expressions and two expressions RS are concatenated.

From what I know, either you must prove using existing rules about equivalence of regular expressions (example: commutativity or associativity of union) or you must prove that L(RS) is a subset of L(SR) AND L(SR) is a subset of L(RS) where L is the language denoted by the regular expression in the parentheses.

However, I am struggling to come up with a proof. Could someone give me a hint?

# Answer
> 3 votes
Let's go with your second approach.

First note that $R^n$, for any nonnegative integer $n$, is in $L(S)$.

If the string $w$ is in the first language, $L(RS)$, then we know that $w$ can be written as the concatenation of some string in $R$ and some string in $S$. This concatenation is denoted $(0 + 1)(0 + 1)^n$ (for some nonnegative integer $n$), which equals $RR^n$ which equals $R^{n+1}$, which equals $R^nR$, which we know is in the language $L(SR)$ (since $S=R^\*$).

The reverse direction is more or less the same thing.

---

Edit: Another interesting way of proving this is to prove $L(RS) = L(S)$ and $L(SR) = L(S)$.

To prove $L(RS) = L(S)$, take any string in $L(RS)$. It can be written as $RR^n$ for some nonnegative integer $n$. Now this equals $R^{n+1}$, which is of course in $L(S)$. So we have that $L(RS)\subseteq L(S)$.

Now take any string in $L(S)$. It can be written as $R^m$ for some nonnegative integer $m$. This is equivalent to $RR^{m-1}$, which is in $L(RS)$, so we know that $L(S)\subseteq L(RS)$.

Therefore we have $L(S)=L(RS)$.

We can prove $L(S)=L(SR)$ in a very similar way. Therefore $L(RS)=L(SR)$.

---

The actual difficulty and intuition behind the proof is fairly trivial, but putting the proof into words is harder. The proof amounts to proving some kind of exponent law for the Kleene star. We don't have an actual exponent law for the Kleene star, so the key part of the proof is simply isolating a single arbitrary string in the language, and then we have the finite integer exponents and we can just use the normal exponent laws.

---
Tags: proof-techniques, regular-expressions
---


title: Why is DPLL better than brute force?

text:
# Question
Title: Why is DPLL better than brute force?
I understand that by being clever about the way we navigate the search space of the SAT problem we're going to get better performance than by randomly choosing and testing solutions, though of course both methods have $O(2^n)$ time complexity. What are the specific reasons that DPLL gives better performance than brute-force (sequentially testing solutions from FALSE-FALSE-FALSE.... to TRUE-TRUE-TRUE....)?

# Answer
> 8 votes
Local (stochastic) search is all about clever navigation of the search space. DPLL's advantage is *pruning* the search space of large swaths of assignments that provably cannot satisfy the formula. DPLL does this by incrementally building partial assignments (some variables assigned values, some left unassigned), applying the unit propagation and pure literal rules and then checking if the resulting formula is trivially unsatisfiable. If the simplified formula implied by the partial assignment contains an empty clause, DPLL need not try assigning values to the remaining unassigned variables since the empty clause represents a clause that can never be satisfied under the partial assignment. The time saved is exponential to the number of unassigned variables, and those skipped assignments are where DPLL improves on brute force sequential search.

---
Tags: satisfiability, sat-solvers
---