Kernels in parameterized complexity Can anyone explain me what (problem-)kernels are and what's the use of them? My slides say:

The kernel of a parameterized problem $L$ is a transformation $(x,k) \mapsto (x',k')$ such that:

$(x,k) \in L \Leftrightarrow  (x',k') \in L$
$|x'| \leq f(k)$ for some function $f$
$k' \leq g(k)$ for some function $g$
transformation must be computed in polynomial time.

My questions are:

How is this connected with a problem being fixed parameter tractable?
What makes kernels useful?
Where does this definition come from.

The example on my slides is for vertex cover, but I don't really get it, cause the slides are kind of short.

Intuitively, a kernelization algorithm is an algorithm which in polynomial time preprocesses a given instance and outputs an instance whose size is bounded in the parameter.  The goal of kernelization is (at least) two-fold.  We get provable performance guarantees, i.e., we can prove upper bounds on the output instance, which has applications both in the design of algorithms, and also as a complexity measure.

More formally a kernelization algorithm (often referred to as the kernel), is an algorithm for a problem which on an input $(G,k)$ outputs an equivalent
  instance $(G',k')$ with $\max\{|G'|,k'\} \leq f(k)$ for some function $f$.
Furthermore, the algorithm needs to run in polynomial time.

The following result shows that the power of kernels is, so to speak, equivalent to the power of fixed parameter tractability (PDF)

Theorem (Folklore).  A problem is fixed parameter tractable if and only if it admits a kernel and  is decidable.

Although the notion of kernel coincides with fixed parameter tractability, there is a stronger version of kernelization where we demand the function $f$ above to be a polynomial.

If you want to see the original definitions, I advice you to pick up Downey and Fellows' book on parameterized complexity, or start from Niedermeier's Habilitation thesis mentioned above.  There is also a Wikipedia article on Kernelization.


Calculate storage requirements for a data set I have a simple problem. I can't seem to even find the right search terms to get me pointed in the direction I need to be heading.

I'm writing a bunch of integers to disk. Lot's of them.

Starting with the integer 2, I add it to another integer, write the result to disk, and start the process again using the result as the seed.

This pattern is helping me generate data I need for other research, but I need to apply this pattern until I've reached integers with a length of 10,000 digits or more.

So, here is my simple question: given a set of data of a known data type, how do I calculate the storage space required to store that set?

At the moment, I'm doing this incredibly simple task in Python, recording longs to disk as binary in a single file. But, on my very small machine, I was only able to store the integers my process produced with values between 0 and 42 billion.

Short of my goal of recording a data set with values between 0 and 1e10000.

Given that I have no exposure to formulas for calculating hardware requirements for storing data like this, I have no idea if I'm using the most efficient language and data type for storing as many integers as possible in as little space as possible.

There are two ways to interpret your dataset generating process. The first produces all even numbers between $2$ and your bound: $2$, $4$, $6$, $8$, …; the second produces all powers of $2$ between $2$ and your bound: $2$, $4$, $8$, $16$, … An integer $N$ requires roughly $\log_{256} N$ bytes to store. Therefore, if your bound is $N$, the first interpretation will take about
$$ \sum_{k=1}^{N/2} \log_{256} (2k) \approx \int_1^{N/2} \log_{256} (2x) \, dx \approx (N/2) \log_{256} N \text{ bytes}. $$
The second interpretation, assuming $N=2^m$, will take about
$$ \sum_{k=1}^m \log_{256} 2^k = \sum_{k=1}^m (k/8) \approx m^2/16 = 4(\log_{256} N)^2 \text{ bytes}. $$


Help with a dynamic programming solution to a pipe cutting problem I'm trying to complete a problem where I have to design and implement a dynamic programming solution to the following problem

  You have to cut a metal pipe into several pieces. To do so, you bring it to a company that charges money according to the length of the pipe being cut. Their cutting method means that only one cut can be made at a time.

  Different ways in cutting the pipe can lead to different overall total prices. For example, suppose that a pipe of length 10 meters has to be cut at 2, 4, and 7 meters from one end. There are several ways to do this. One way is to first cut at 2, then 4, and then at 7. This gives a price of 10 + 8 + 6 = 24 because the first pipe was 10 meters in length, the second was 8 meters, and the third was 6 meters in length. Another way is to cut at 4, then at 2, then at 7. This would give a total price of 10 + 4 + 6 = 20, which is a cheaper price.

  Figure out (a method to determine) what is the cheapest price that is possible (to make sure that the company isn't cheating you). The procedure that you write (in Java) should return a single integer, which will be the cheapest possible total cost for performing all of the cuts. Only one cut can be performed at a time, and the cost of making a cut is equal to the length of the pipe being cut (before the cut is performed).

But I'm having trouble knowing where I even need to start. If anyone could point me in the direction of where I can research similar problems or give me an idea of what I should be thinking about with this problem it would be great.

For me, it makes more sense to think about this problem in reverse.  The problem is posed as a destructive process - you have 1 pipe, and you split it into many.  However, in terms of the cost calculation, the reverse process results in the same answer.  That is, if you take the resulting pipe segments and start gluing them back together, using the sum of the length of the two pieces you're gluing as the cost of the operation, you end up with the same cost.

So then the question becomes the following:

given a set of pipe segments, what is the cheapest order of gluing segments together until you  have only one segment?  This assumes a cost function where c(x1,x2) = len(x1) + len(x2).

This is trivial when you have two segments.  There's only one way to glue them together, so that has to be the cheapest way.

With three segments, it starts to be a bit more interesting.

Lets say we have lengths x1, x2, and x3.  We have three options for our first operation:
x1 + x2, x2 + x3, and x1 + x3.  No matter what values are in x1, x2, and x3, the operation after this one will cost the same.  That is to say the following:

(x1 + x2) + x3 == (x2 + x3) + x1 == (x1 + x3) + x2

As a result, the cheapest way of putting the three pieces of pipe back together is going to be the way that has the cheapest first step.

Then the question becomes, which of the first steps is the cheapest?

That depends on what the values in x1, x2, and x3 are.  Lets assume the three values are in ascending order.  So x1 <= x2 <= x3.  Now you can determine which starting pair is the cheapest, right?  Its the pair containing the smallest values, or x1 and x2.  Note that there is the possibility that two or more of the three values are the same.  I'll leave it up to you to convince yourself that such a scenario is not a problem.

So we've got a solution for either 2 or 3 pieces.  This should give you some insight towards a general solution.


What is an oracle separating IP and PSPACE? I saw this link on cstheory:

https://cstheory.stackexchange.com/questions/6634/is-there-an-oracle-that-separates-two-complexity-classes-known-to-be-equal

but it did not provide specific details.  Can anyone tell me what the specific oracle is (or direct me to a paper which does)?  Also on a meta-level why does this not call into question the legitimacy of oracle Turing machines- if two classes coincide, how can they be separated?  Thanks.

The answer to the question you link contains all the information you need. The multi-authored paper The random oracle hypothesis is false proves the stronger result that IP and PSPACE are different with probability 1 with respect to a random oracle. They also comment that a concrete oracle under which IP differs from PSPACE can be constructed using standard techniques, by which they mean the form of diagonalization used to separate P from NP with respect to a concrete oracle; they do not provide any details, though. Presumably it is a not too difficult exercise.

The meta-question is addressed both in the answer you link and in the paper. I suggest you first read the paper, and then if you have more questions, you can ask them here in this site.


Is a DTM with k-tapes not the same thing as a NDTM with k-branches? In the definition of a complexity class like P, where they reference Deterministic Turing machines (DTMs), I don't see any restriction on # of tapes these DTMs are allowed to use.

If a language L is in P do all its words have to be decidable in polynomial time by a 1-tape, 2-tape,....k-tape Turing machine in polynomial time?

Let $\mathsf{P^k}$ be the class of problems solvable in polynomial time on deterministic Turing machines with $k$ tapes. Then
$$
\mathsf{P^1} = \mathsf{P^2} = \mathsf{P^3} = \mathsf{P^4} = \mathsf{P^5} = \cdots
$$
Let $\mathsf{PD^{d}}$ be the class of problems solvable in polynomial time on deterministic Turing machines with access to a $d$-dimensional infinite tape. Then
$$
\mathsf{P^1} = \mathsf{PD^1} = \mathsf{PD^2} = \mathsf{PD^3} = \mathsf{PD^4} = \mathsf{PD^5} = \cdots
$$
Similarly, $\mathsf{P}$ is also the class of problems solvable in polynomial time on RAM machines, which have a random-access memory (i.e. you can implement indexing $A[i]$ without needing the head to scan to the $i$th position of the tape).

The definition of $\mathsf{P}$ is very robust to the particular machine model used, and this makes $\mathsf{P}$ a very natural complexity class. This is similar to the class of all decidable languages, which can be defined in countless ways. The exact way you define $\mathsf{P}$ is arbitrary, since all definitions amount to the same complexity class.

The story gets a bit more complicated when we consider computation models other than deterministic machines (of any kind). For example, are probabilistic polytime algorithms stronger than deterministic ones? The answer might depend on the error. Probabilistic polytime algorithms with constant error probability define the complexity class $\mathsf{BPP}$, which is believed (by most) to be the same as $\mathsf{P}$. If we allow unbounded error we get $\mathsf{PP}$, which contains $\mathsf{NP}$, and so such algorithms are probably more powerful than deterministic ones. Similarly, quantum algorithms with bounded errors form the complexity class $\mathsf{BQP}$, which contains problems such as factoring which are not believed (by most) to be solvable in classical polynomial time.


Search for maximal value smaller than V in an array composed of K linear functions Sorry for the lack of clarity in the question description.

I have an array composed of length $N$ composed of $K$ linear subarrays. We define a linear subarray as a contiguous subarray of the array $[l,r]$ where $A[i]-A[i-1] = C$, a constant, for all $l<i<=r$. (Note: $C$ may be different for different subarrays; the elements of the array are integers.) Please note that the linear subarrays are not disjoint (there is one element intersection between any pair of adjacent linear subarrays). For example, [1,3,5,4,3,2] has two linear subarrays: [1,3,5] and [5,4,3,2]. [1,3,5,1,2,3] would have three: [1,3,5], [5,1], [1,2,3].

I wish to find multiple queries for the maximal value that is less than a queried value $V$, in $o(K)$ and $o(N)$ time per query, with $o(K^2)$ and $o(N)$ preprocessing. (Assume that the array has already been stored in terms of the K linear subarrays, perhaps in terms of the constant C and length of each subarray, with the subarrays ordered. Therefore, you are given the array with the starting and ending points of all the linear subarrays, as well as the linear constant C, as described before. So, one does not need to derive the linear subarrays in the first place.) Otherwise, a proof (formal or not) that it is not possible to do so would be appreciated.

Of course, a balanced binary search tree (BBST) or simply sorting achieves the purpose, but it requires $O(NlogN)$ preprocessing, which is too much. Checking the largest valid value within each subarray takes $O(K)$ per query, which is again too much. Would it be possible for something to combine both of these, perhaps?

Randomised algorithms are okay as long as they always achieve the correct answer and work fast enough in the average case, though deterministic algorithms are preferred.

Thanks for any and all responses. I was wondering if there was any research in the question, maybe? It does not seem like too obscure a topic, but unfortunately my searching has not been competent enough.

EDIT: A method that seems useful.

Here was my line of thinking after I asked the question; I wonder if this would help somehow. It uses the idea of modulo as well.
Initialise V=0, and allow each linear subarray to be stored as L,R; where L is the minimal value of the subarray and R is the maximal value. When we are given a query for V, we somehow disinclude elements where L>V and R<V (perhaps by using multiple dimensions?) A supplementary data structure stores the minimal theoretical difference of the element in the array, which is something like L - V mod c[i]. So essentially, we now need to be able to run a range add on this data structure, but if the value of any element becomes <0 or >=c[i] it needs to be reset (eg. if an element becomes equal to -1 with c[i]=5 it would be reset to 4; if an element becoming equal to 6 with the same c[i] would be reset to 1); and also run range minimum queries.

If such a data structure can be made, the problem is solved. The trouble is the modulo, as range add and range minimum query can be easily done with a segment tree and lazy propagation; as well as the disinclusion of certain elements.

It is not possible to guarantee to find the maximal value that is less than a queried value $V$ in $o(K)$ time with preprocessing in $o(N)$ time.

This can be seen easily in the following extreme case. Let $A$ be any array of $N$ integers, which is composed of the following $K=N-1$ linear subarrays.

the subarray $A[0], A[1]$ with $C=A[1]-A[0]$.
the subarray $A[1], A[2]$ with $C=A[2]-A[1]$.
$\cdots$
the subarray $A[N-2], A[N-1]$ with $C=A[N-1]-A[N-2]$.

With $o(N)$ time preprocessing and $o(K)=o(N)$ time processing, an algorithm will not be able to even read some number in $A$ when $N$ is large enough. (In fact, most of the numbers in $A$.) So, for some queried value $q$, the algorithm will fail to recognize that $q+1$ appears in $A$.

(The explanation above could be made more rigorous, for example, using the formal method of adversary and a well-defined model of computation.)

It looks like the more interesting question to ask should be whether there is an algorithm with $o(N\log N)$ preprocessing and $o(K)$ per query. Or whether there is algorithm with $o(N)$ preprocessing and $o(K)$ per query given $K=o(N)$. That sounds like another question, anyway.


Is relational algebra a procedural, imperative, and/or declarative language? In Database System Concepts 6ed,

6.2 The Tuple Relational Calculus
When we write a relational-algebra expression, we provide a sequence of procedures that generates the answer to our query.
The tuple relational calculus, by
contrast, is a nonprocedural query language. It describes the desired information
without giving a speciﬁc procedure for obtaining that information.
A query in the tuple relational calculus is expressed as:
{t | P(t)}. That is, it is the set of all tuples t such that predicate P is true for t.

Does the above mean that relational algebra is a procedural language?
Is relational algebra a declarative language?
Is the tuple relational calculus  a declarative language?
Is the tuple relational calculus more declarative than relational algebra is?
Is a procedural language  an imperative language? (This is always what I heard, but I also  heard that SQL is a declarative language (so is relational algebra) so is not imperative.)
What is the correct or most reasonable or most accepted definition of procedural languages, imperative languages, and declarative languages?
Thanks.

The terminology used in the database area calls the relational algebra “procedural” to contrast it with the languages based on “calculus”, since an algebraic expression describes an ordered set of steps to find the result: simply execute the operations in the correct order to produce the result.

In contrast, in an expression of a calculus based language, the result is described through a property that holds on it, without specifying which operations should be applied to find it, neither the order in which they should be applied. So it “declares” the properties of the result, not a “procedure” to obtain it.

This terminology has no particular relations with other terminologies in the field of programming languages (like imperative, functional, applicative, etc.)


What would be the real-world implications of a constructive $P=NP$ proof? I have a high-level understanding of the $P=NP$ problem and I understand that if it were absolutely "proven" to be true with a provided solution, it would open the door for solving numerous problems within the realm of computer science.

My question is, if someone were to publish a indisputable, constructive proof of $P=NP$, what are some of the immediate effects that we would see of such a discovery?

I'm not asking for opinionated views of what the world would look like in 5-10 years.  Instead, it is my understanding that this is such a fundamentally unsolvable problem that it could radically change the way we compute... many things (yeah, this is where my ignorance is showing...) that we can't easily calculate today.

What kind of near-immediate effect would a thorough, accurate, and constructive proof of $P=NP$ have on the practical world?

People have given good answers assuming that $P=NP$ with some really large constant. I'm going to play the optimist and assume that we find a proof of $P=NP$ with a tractably small constant. Perhaps not likely, but I'm going to try to give some insight into what sorts of things would happen if we could efficiently solve all $NP$ problems.

Compilers: Some computer programs would get slightly faster, since compilers use graph coloring for register allocation. We would be able to allocate for large numbers of registers exactly. Existing compilers using an approximate solution (like chordal graphs) would get better output, and those using an exact solution would get faster.
Facility location: Businesses would be able to find the optimal place to place factories and supply depots to ship to their stores, when there are possibly thousands of stores and factories. Would likely not be a huge improvement over modern approximations, but would reduce costs.
Buying plane tickets: airline tickets are weird since they don't follow triangle equality. Sometimes it's cheaper to fly from A -> B -> C than directly from A -> C, something that doesn't come up when modelling distances. It would be easy to make a website that finds the absolute cheapest sequence of flights that visit some number of cities and starts and ends in your hometown.
Circuit design: electrical circuits on a chip are basically Boolean formulas. Things like minimization could be efficiently calculated, so our hardware would get a bit more efficient.
Scheduling: mad that your school put two of your exams on the same time? If $P=NP$ your school could either how many timeslots they need so no student has a conflict, or given a number of time slots, minimize the number of conflicts.

This is just a sampling of practical applications that we'd see if $NP$-completeness weren't a barrier. I'm sure I've missed many, but if the given construction had a good constant, the implications would be far reaching.


Formalizing basic category theory in Coq I'm a total beginner in Coq and I'm trying to implement some category theory stuff as an exercise.

I surfed a little among git repos of the many avaible such implementations (HoTT, Awodey's Coq companion, etc.) it seems that every single project implements something like that

Record Category : Type :=
  mkCategory{
    ob : Type ;
    mor : ob -> ob -> Type ;
    compose : forall x y z : ob,
                mor x y -> mor y z -> mor x z ;
    identity : forall x, mor x x ;
    (* ... axioms ... *)
  }.

It is kind of natural, considering most definition of categories in modern book. However, I feel that it would be easier to implement it internally (if not mistaken, it was the common definition at Grothendieck's time) :

  Definition. A category is the data of

  a set/class $\rm Ob$ of objects,
  a set/class $\rm Mor$ of morphisms,
  functions $s,t \colon {\rm Mor} \to {\rm Ob}$, and $i \colon {\rm Ob} \to {\rm Mor}$ ($s$ stands for source, $t$ for target, and $i$ for identity)
  a function $\circ \colon {\rm Mor} \times_{s,t} {\rm Mor} \to {\rm Mor}$ whose domain is the fiber product of $${\rm Mor} \stackrel s \to {\rm Ob} \stackrel t \leftarrow {\rm Mor}$$

  satisfying some axioms...

The advantage of such a definition is that it generalizes directly by replacing "set/class" by "objects of some category" and "functions" by "morphisms of this category", leading to the concept of internal category. (Then you can talk of topological/differential categories, or categories inside a topos, etc.)

My problem is to formalize the fiber product in Coq. My first attemp would be to do something like

Record Category : Type :=
  mkCategory{
    ob : Type ;
    mor : Type ;
    s : mor -> ob ;
    t : mor -> ob ;
    compose : mor -> mor -> option mor ;
    i : ob -> mor ;

    adequacy : forall f g : mor,
                 (exists h, (compose f g) = (some h)) -> (t f = s g) ;
    (* ... axioms ... *)
  }.

But I feel that could lead to some curbersome later code. For example, chained compositions would be difficult to read.

Is there a project with an implementation based on the internal definition? Is there a quick way to define the fiber product I need in Coq?

Edit. By the way, I see a lot of

Ob :> Type

rather of

Ob : Type

What is the meaning of the extra ">"? From the doc, it seems it is some kind of coercion. What exactly does this mean?

A natural way to write down what you want is to restrict the type of composition to only the "composable" morphisms:

$$ \mathrm{compose}:\forall f\ g: \mathrm{mor}, t(f) = s(g)\rightarrow \mathrm{mor}$$

adding, of course, the conditions:
$$ s(\mathrm{compose}\ f\ g\ e)=s(f)$$
$$ t(\mathrm{compose}\ f\ g\ e)=t(g)$$

This works, as it now only allows composing functions that are provably composable. This roughly corresponds to the fibered product in category theory you were mentioning.

However is somewhat awkward as it adds proof obligations to every application of compose, which can quickly become unmanageable (even expressing associativity is hard!). Also it somewhat precludes adding the notation $\circ=\mathrm{compose}$, since compose takes 3 arguments.

This is a somewhat common problem in type theory, which results from the fundamental tension of having partial functions in a total language.

Another, less elegant solution, is to define composition to be everywhere defined:
$$ \mathrm{compose} :\mathrm{mor}\rightarrow\mathrm{mor}\rightarrow\mathrm{mor}$$
and guard every theorem involving composition with well-definedness conditions:

$$\mathrm{assoc}:\forall f g h:\mathrm{mor}, t(f)=s(g)\wedge t(g)=s(h)\Rightarrow\\ \mathrm{compose}\ f\ (\mathrm{compose}\ g\ h) = \mathrm{compose}\ (\mathrm{compose}\ f\ g)\ h $$
This essentially means:

  compose is defined everywhere, but the definition is only meaningful if applied to composable morphisms.

This approach also has drawbacks, mostly the gargantuan quantity of proof obligations that follow every application of the basic axioms.

I'm afraid you have to choose your poison in this case, or come up with a clever way to do better...


How to convert two conflicting objective functions into a single objective function I have two objective functions say f1 where I have to minimize (X+Y) and another function f2 where I have to maximize (A-B). The two functions are conflicting.

I need to convert them into a minimization problem involving one single objective function using the weighed sum approach where the final form would become f3 = Min {uf1 (+ or-) vf2} where u+v=1.

I am not sure what would be the sign before vf2 ? I wonder if it should be f3 = Min {uf1 + vf2} or f3 = Min {uf1 - v*f2}.

Thanks in advance.

To turn a maximisation problem into a minimisation one (or vice versa), simply multiply the value by -1.

Hence you want w1 * f1 - w2 * f2, for some appropriate choice of weights w1, w2 (which could indeed both be 1).

Unless there's some other requirement you haven't mentioned, there's no specific need for w1 and w2 to add up to 1: it depends on the relative importance of f1 and f2, which is problem-specific.


What is meant by the term "prior" in machine learning I am new to machine learning. I have read several papers where they have employed deep learning for various applications and have used the term "prior" in most of the model design cases, say prior in human body pose estimation. Can someone explain what does it actually means. I could only find the mathematical formulation of prior and posterior in the tutorials.

Put simply, and without any mathematical symbols, prior means initial beliefs about an event in terms of probability distribution. You then set up an experiment and get some data, and then "update" your belief (and hence the probability distribution) according to the outcome of the experiment, (the posteriori probability distribution).

Example:
Assume we are given two coins. But we don't know which coin is fake. Coin 1 is unbiased (HEADS and TAILS have 50% probability), and Coin 2 is biased, say, we know it gives HEADS with probability 60%. Mathematically:

Given we have HEADS, the probability that it is Coin 1 is 0.4 $$p(H | Coin_1) = 0.4$$ and probability it is Coin 2 is 0.6 $$p(H| Coin_2) = 0.6$$

So, that is all what we know before we set up an experiment.

Now we are going to pick a coin toss it, and based on the information what we have (H or T) we are going to guess what coin we have chosen (Coin 1 or Coin 2).

Initially we assume $p(Coin_1) = p(Coin_2) = 0.5$ both coins have equal chances, because we have no information yet. This is our prior. It is a uniform distribution.

Now we take randomly one coin, toss it, and have a HEADS. At this moment everything happens. We compute posterior probability/distribution using Bayesian formula:
$$p(Coin_1 | H) = \frac{p(H | Coin_1)p(Coin_1)}{p(H | Coin_1)p(Coin_1) + p(H | Coin_2)p(Coin_2)} = \frac{0.4\times0.5}{0.4\times0.5 + 0.6\times0.5} = 0.4$$

$$p(Coin_2 | H) = \frac{p(H | Coin_2)p(Coin_2)}{p(H | Coin_1)p(Coin_1) + p(H | Coin_2)p(Coin_2)} = \frac{0.6\times0.5}{0.4\times0.5 + 0.6\times0.5} = 0.6$$

So, initially we had $0.5$ probability for each coin, but now after the experiment our beliefs has changed, now we believe that the coin is Coin 1 with probability 0.4 and it is Coin 2 with the probability 0.6. This is our posterior distribution, Bernoulli distribution.

This is the basic principle of Bayesian inference and statistics used in Machine learning.


Printing all paths of a tree and sorting the weight of edges Let $T=(V,E)$ be tree and each edge has a positive scalar weight. I need to print all paths in the tree and then sort the weight of edges in each paths. it needs $O(n^3\log(n))$ time.   To solve this problem we can rooted the tree in a leaf and print all vertices by preorder algorithm and in each step we insert the new edge weight. After meeting all vertices we can delete the root and consider another leaf as the root. The complexity seems $O(n^2\log(n)).$ Can we reduce the complexity, for example, $O(n^2)$?

You can't do better than $\Omega(n^3)$ running time.

In a tree, there is a path between every pair of vertices, so there are $\Theta(n^2)$ paths.  The average path length can be $\Theta(n)$.  So the total length of the output can be $\Theta(n^3)$.  Obviously, no algorithm can run faster than that, since it takes at least $\Theta(n^3)$ time just to write out the output.


Difference between reductions in algebraic problems versus reductions in computational intractability When I read about NP-completeness for the first time, I really wondered why is the concept of reductions given such high emphasis, after all we have been looking at concepts such as reductions and 'special case of one another problem' in mathematics since elementary algebra. What I mean by reductions in algebra is the following.

Problem 1: Find value of x such that $x^2+ax+b=0$

Problem 2: Find value of x such that $(x+m/n)^2=0$

We can go on proving both the problems are same and one solution can be translated to another.

My question is that "Is the concept of reductions in computational intractability same as that in above algebraic theory?" If not, how are the reductions in CI theory different?

Reductions in computational complexity are similar to the reduction you described, but are usually given with bounds on the time or space. To be useful, these bounds are usually inconsequential (ie. the same or smaller) to the bounds of solving the problem.

Reductions in computational complexity are about converting one problem to another equivalent one. Usually one would also give bounds on how hard (how much time/space) a reduction takes as well. For example, all NP-complete problems have reductions to each-other, and their reductions are polynomially bounded. Since algorithms solving NP-complete problems are suspected to take exponential time on a deterministic Turing machine, the polynomial time reductions are inconsequential (compared with the time of actually solving the reduced problem), and thus these reductions make all of the NP-complete problems essentially equivalent. There can reductions between problems in other classes of complexity as well, and to be useful they would likely be bounded by something considered inconsequential to solving them.


Overall time complexity of Heuristical Algorithm for travelling salesman problem [TSP] I am trying to figure out the time complexity of a heuristical algorithm used to solve the Travelling Salesman Problem in a more efficient way than by brute force, ($\theta(n!)$ or similar)

The first step is to compute Kruskal's Minimum Spanning Tree, which to my best knowledge is of
$\theta(E+V)$, where E is the number of edges of the graph, and V the number of vertices.
Next, the algorithm finds a minimum-length pairwise matching of the odd degree vertices from the result of the MST graph. Min pairwise matching can solved in $\theta (V'logV')$, where $V'$ represents the vertices that are of odd deg.

My question is, what is the overall time complexity of my Heuristical Algorithm, is it the sum of the two time complexities of 1 and 2?

For further reading on the heuristical algo, consult http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.6.html

Thanks,

Any algorithm that first does $A$ of work and then $B$ of work will have done a total of $A+B$ of work. It doesn't matter what the algorithm is, or what $A$ or $B$ are.

You might be getting confused by steps that look complicated and/or by the fact that $A$ and $B$ are expressed in terms of $\Theta$. For this reason and in general, it is a good idea to try to compute $A+B$ as well as possible, and then finally expressing the sum in terms of Big Oh. Otherwise, you run the risk of performing voodoo, and not really understanding what $\Theta$ means.


How do we know INVERSIONS-COUNT algorithm implemented in balanced tree really works? How do we know INVERSIONS-COUNT algorithm (exercise 14.1-7 from here), implemented in balanced tree really works?

We assume that the tree data structure we're using is an order statistic tree which means that a) it's a balanced binary tree, b) each node $x$ is augmented with $size$ field which tells us the size of the node's subtree (its inner nodes, including $x$).

We also have an array $L[1..n]$ which contains the values of the keys of the tree (not necessarily sorted).

The algorithm uses two helper functions:

RANK(Tree, node_x) - returns the rank of the key of node_x in array $L$.

SEARCH(Tree, L[i]) - returns the node with the same key as the element $L[i]$ in the given array.

This is the code:

Construct an order statistic tree T for all the elements in L
   t = −|L|
   for i from 0 to |L| − 1 do
      t = t + RANK(T, SEARCH(T, L[i]))
      remove the node corresponding to L[i] from T end for
   return t

If the array is sorted then there're no inversions. Therefore t is incremented each time by $1$ because in sorted array each new element is the minimal one and has rank $1$ (because we delete the last node).

If the array is not sorted then why are we guaranteed that the ranks will at some point "overtake" t and produce the correct amount of inversions?

At step $i$, the rank of $L[i]$ in $T$ is the number of elements in $L[i],\ldots,L[|L|-1]$ which are at most $L[i]$. Taking into account the $-|L|$ in the beginning, we see that the algorithm counts the number of pairs $i<j$ such that $L[j] \leq L[i]$, which is exactly the number of inversions (assuming all elements are distinct).


Can we use reductions to design approximation algorithms for NP-hard problems? Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is the size of the input of problem $Q$) to $P(n)$ and showed that $P(n)$ is NP-hard. The time complexity of the reduction is $O(n^k)$ for some fixed $k$.

Can I use a known approximation algorithm for problem $Q(m)$ that is $O(f(m))$-approximation for problem $Q(m)$ to design an approximation algorithm for problem $P(n)$ that is $O(g(n))$-approximation for problem $P(n)$?

Yes, but you need an approximation-preserving reduction in the opposite direction.


Creating a grammar from the language L = { a^n b^2n a^(n+2) : n>=1 }

So I'm trying to construct the grammar and I'm getting stuck.Some example strings would be these (spaced out to help demonstrate the patterns):

a bb aaa

aa bbbb aaaa

aaa bbbbbb aaaaa

This is what I have so far....

S -> aXbbXaaa

XbbX -> bXbbXb

The first rule says that there will always be an a on the left side, 3 a's on the right, and 2 b's in the middle.

The second rule adds 2 b's to the middle for b^2n.

But I can't figure out a way to get the a's....

Any suggestions? I don't want the exact answer, but rather hints to lead me to a solution. Thanks in advance!

Hint: The language is not context-free. So you will need to employ a type of grammar that is more powerful. Context-sensitive grammars can do the job.

If you need guidance in how to build a context-sensitive grammar for such a language, you might want check a context-sensitive grammar for $a^nb^nc^n$.


Hardness proof of EVEN-ODD PARTITION The PARTITION problem is NP-complete:

INSTANCE: finite set $A$ and a size $s(a) \in \mathbb{Z}^+$ for each $a \in A$
QUESTION: Is there a subset $A' \subseteq A$ such that $\sum_{a \in A'} s(a) = \sum_{a \in A \setminus A'} s(a)$

The problem remains NP-complete even if the elements are ordered as $a_1,a_2,...,a_{2n}$ and we require that $A'$ contains exactly one of $a_{2i-1},a_{2i}$ for $1 \leq i \leq n$ (Garey and Johnson, Computers and Intractability).

This variant should be known as EVEN-ODD PARTITION.

Do you see a quick reduction to prove its hardness? (or do you know the paper where it was first defined and proved)

Let $b_i = a_{2i} - a_{2i-1}$. The problem is then finding $\sum \varepsilon_i b_i = 0$. Here $\varepsilon_i = 1$ if $a_{2i} \in A'$ and $-1$ otherwise. Let $B' = \{b_i \mid \varepsilon_i = 1\}$. Note that $\sum_{b \in B'} b = \sum _{b \in B \setminus B'} b$. Thus solving PARTITION of $B$ would solve EVEN-ODD PARTITION of $A$.

Let $b_{2i} = a_i$ and $b_{2i-1} = 0$. Note that if $b_{2i} \in B' \leftrightarrow a_i \in A'$ and $\sum_{B'} = \sum_{B \setminus B'}$ then $\sum_{A'} = \sum_{A \setminus A'}$. Thus solving EVEN-ODD PARTITION on $B$ would solve PARTITION on $A$.


Select largest subset, subject to a separate weighting constraint Given an unsorted set of tuples $(c, w)$ and a threshold value $W$, I want to select $k$ tuples such that:
$$
maximize\sum_{i=1}^k c_i \\
\sum_{i=1}^k w_i \ge W
$$
It seems pretty simple at first. Without the weighting constraint, you can use any selection algorithm to select the $k$ elements with largest $c$. But with the weighting, it seems there's no special structure to exploit. Seems like you'd have to search all subsets?

Use dynamic programming.

Let the $(c,w)$ pairs be $(c_1,w_1),\dots,(c_n,w_n)$.  Define $A[k^*,n^*,W^*]$ to be the largest possible sum of $c$-values obtainable by selecting $k^*$ pairs from $(c_1,w_1),\dots,(c_{n^*},w_{n^*})$ such that the sum of their $w$-values is at least $W^*$.  Then you can write down a recursive definition of $A[k^*,n^*,W^*]$:

$$A[k^*,n^*,W^*] = \max(A[k^*,n^*-1,W^*], A[k^*-1,n^*-1,W^*-w_{n^*}]+c_{n^*}).$$

Now fill in this table using dynamic programming.  The running time will be $O(nkW)$, where $n$ is the number of $(c,w)$-pairs in the input.

This is basically an adaptation of the dynamic programming algorithm for the knapsack problem: https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem


Running time of sparse matrix multiplication Given a sparse matrix $M \in \mathbb{R}^{n \times m}$ with $n \ll m$ and $\mathsf{nnz}$ being the number of non-zero-components. What is the running time of computing $M M^T$?

The question doesn't make any sense. It doesn't make sense to ask for the running time of a computation, unless you specify an algorithm for that computation. So how would you calculate this product? That's the first thing you need to do: Specify an algorithm how you calculate the product.

The next step: Assuming that many array elements are zero, can you reduce the amount of work that this algorithm would be doing? For example, if you know that x = 0, then it's pointless to multiply xy because you know the result is 0. And it's pointless to add xy to z, because that doesn't change z. So how can you take advantage of many array elements being zero? What's the runtime if you do that?

The next step: Assuming that many array elements are zero, can you reduct the amount of work further? Would you need some clever data structures? If yes, which ones?


Algorithm for a list of best solutions to the Assignment problem I am trying to brute force a classical substitution cipher. The problem is that there are $26!$ possible keys. So, I'd like to do frequency analysis to try likely keys first. Then, on the first $n$ tries I will use a dictionary to see if there are actual words in the decryption. That way, I don't need to try all possible keys.

So, as suggested here, I will use chi-squared testing. I was thinking of making a matrix, best illustrated with an example. Suppose in an alphabet {A,B,C} the letter frequencies are 50%, 30% and 20% respectively, and that in a ciphertext the frequencies are 10%, 50% and 40% respectively. Then the A-B cell in the matrix is $(0.1-0.3)^2=0.04$, which is the error rate when a B in plain is encrypted as an A.

   |  A   |  B   |  C                 | Use in plaintext | in ciphertext
---+------+------+------           ---+------------------+---------------
 A | 0.16 | 0.04 | 0.01             A |        0.5       |       0.1
 B | 0.00 | 0.04 | 0.09             B |        0.3       |       0.5
 C | 0.01 | 0.01 | 0.04             C |        0.2       |       0.4

The Hungarian algorithm then gives me a frequency-analysis-wise optimal key: $A \mapsto C, B \mapsto A, C \mapsto B$. This is because the sum of the errors (0.01+0.00+0.01=0.02) is minimal. This is useful, but what I need is the $n$ best keys.

The only thing I can come up with is to run the Hungarian algorithm, and then set one of the cells in the matrix above corresponding to the key found to a high value, so that if you run the algorithm again the  key you find doesn't contain the mapping. So, in the example above, you could set A-C to 1 so that when you run the Hungarian algorithm again you find a different key that doesn't contain $A\mapsto C$.

However, this isn't guaranteed to find good keys in order. What would be a better way to extend the Hungarian algorithm to find the best $n$ keys?

Epilogue: after implementing this using D.W.'s approach below, it turned out that this method doesn't perform well enough to crack small-length (at least up to 1000 letters) cipher texts, because frequency analysis alone isn't enough. Performance may be improved by taking frequent digrams or trigrams into account, but I doubt this method can be as powerful as simple hill climbing.

Here's one technique to enumerate the best $n$ assignments, for any instance of the assignment problem.  I suspect my approach isn't optimal, but it does run in polynomial time: it uses $O(nm)$ invocations of the Hungarian algorithm, where $m$ denotes the number of agents in the problem instance.  In your example, $m=26$, so my approach requires $O(n)$ invocations of the Hungarian algorithm.

Let $A_1,A_2,A_3,\dots$ denote the assignments, from best to worse.  $A_1$ is the best assignment; $A_2$ is the next-best; and so on.  Our goal want to enumerate $A_1,\dots,A_n$.

You can find $A_1$ by solving the original assignment problem, e.g., with the Hungarian algorithm.

How can we find $A_2$, the second-best assignment?  The idea is to use a case analysis.  Let $v_1,\dots,v_m$ denote the $m$ agents in the problem instance, and let $A(v)$ denote the task assigned to agent $v$ by assignment $A$.  We'll break down the space $\mathcal{S}$ of possible candidates for $A_2$ (i.e., the space of all assignments other than $A_1$) into the disjoint union $\mathcal{S} = \mathcal{S}_1 \cup \dots \cup \mathcal{S}_m$, where $\mathcal{S}_i$ is the space of assignments that agree with $A_1$ for $v_1,\dots,v_{i-1}$ but disagree with $A_1$ on $v_i$.  (In other words, we look at the first agent that receives a different assignment in $A_1$ vs $A_2$.  Then there are $m$ possibilities for that agent; we let $i$ denote its index, i.e., the index of the first agent whose assignment in $A_1$ is different from its assignment in $A_2$.  This breaks down the space $\mathcal{S}$ into subspaces $\mathcal{S}_1,\dots, \mathcal{S}_m$, as listed before.)

Now the approach will be to find the best assignment in each $\mathcal{S}_i$, separately.

$\mathcal{S}_1$: We find the best assignment $A$ such that $A(v_1) \ne A_1(v_1)$ using one invocation of the Hungarian algorithm, by changing the cost of the edge $(v_1,A_1(v_1))$ to $\infty$ (or some very large positive number) and then re-running the Hungarian algorithm.  This finds the best assignment out of all assignments that assign $v_1$ to something different than $A_1$ did.
$\mathcal{S}_2$: We find the best assignment $A$ such that $A(v_1) = A_1(v_1)$ and $A(v_2) \ne A_1(v_2)$ using one invocation of the Hungarian algorithm: change the cost of the edge $(v_1,A_1(v_1))$ to $0$, and change the cost of the edge $(v_2,A_1(v_2))$ to $\infty$.
$\mathcal{S}_i$:  Similarly, for each $i$, we can find the best assignment $A$ such that $A(v_j) = A_1(v_j)$ for all $j=1,2,\dots,i-1$ and such that $A(v_i) \ne A_1(v_i)$, using one invocation of the Hungarian algorithm.

This gives us $m$ assignments, i.e., $m$ candidates for $A_2$.  By construction, each one of these assignments is different from $A_1$.  Also, by construction, this covers all the space of all assignments that are different from $A_1$.  Therefore, $A_2$ will be the best of these $m$ candidates, so we can just compare these $m$ candidates and call it $A_2$.

That find the second-best assignment.  How can we find $A_3$, the third-best assignment?  Well, the same ideas apply: we'll use a case split, but now the case-split will be a little more involved.  Suppose that $v_i$ is the first agent where $A_1$ and $A_2$ disagree (i.e., $A_1$ and $A_2$ agree on $v_1,\dots,v_{i-1}$ but disagree on $v_i$, so that $A_2 \in \mathcal{S}_i$).  Then we can break down the space of possibilities for $A_3$ by looking at the first agent that receives a different assignment from $A_2$, or from $A_1$.

In particular, let $\mathcal{T}$ denote the space of possible candidates for $A_3$ (i.e., the space of all assignments other than $A_1$ or $A_2$).  We can partition it into the disjoint union

$$\mathcal{T} = \mathcal{S}_1 \cup \dots \cup \mathcal{S}_{i-1} \cup (\mathcal{T}_1 \cup \dots \cup \mathcal{T}_m) \cup \mathcal{S}_{i+1} \cup \dots \cup \mathcal{S}_m.$$

In other words, since $A_2 \in S_i$ and we now want to exclude $A_2$ from the space of allowable assignments, we partition $S_i$ into $S_i = \{A_2\} \cup \mathcal{T}_1 \cup \dots \cup \mathcal{T}_m$ and remove $A_2$.  Here $\mathcal{T}_j$ denotes the set of assignments that agree with $A_2$ on $v_1,\dots,v_{j-1}$ but disagrees with $A_2$ on $v_j$ (and, if $j=i$, disagrees with $A_1$ on $v_j$ as well).

Now, we use the Hungarian algorithm to find the best assignment in each of $\mathcal{S}_1, \dots, \mathcal{S}_{i-1}, \mathcal{T}_1, \dots, \mathcal{T}_m, \mathcal{S}_{i+1}, \dots, \mathcal{S}_m$.  This is doable using the techniques shown above, using one invocation of the Hungarian algorithm per subspace.  Finally, we let $A_3$ be best of all the solutions found.

We can continue in this way, at each step identifying the next-best by decomposing the space of remaining assignments into multiple subspaces and invoking the Hungarian algorithm on each subspace.  At each step, we introduce at most $m$ new subspaces, and we can reuse the previously-obtained results for the other subspaces.  Therefore, on each step we make at most $m$ invocations of the Hungarian algorithm, so the total number of invocations of the Hungarian algorithm is $O(nm)$.

There's probably a better way to do it, but if you can't find any other algorithm, this is one you could use.  Note that this is a general technique for problem of enumerating the $n$ best assignments to any instance of the assignment problem.  It's not specific to your substitution-cipher example.


Query about FP Divide latency and Initiation Interval Latency is defined as the number of intervening cycles between an instruction that produces a result and an instruction that uses the result. The initiation or repeat interval is the number of cycles that must elapse between issuing two operations of a given type.

In the Appendix C, pages 52-54 of Computer Architecture: A Quantitative approach 5th edition, it was mentioned that

the FP adder is of 4 stages and pipelined, so latency =3(No. of pipeline stages -1) and initiation interval =1 (as pipelined)
the FP multiply is of 7 stages  and pipelined, so latency =6(No. of pipeline stages -1) and initiation interval =1 (as pipelined)

So for
3. The FP divide of 24 stages and unpipelined, so latency =23(No. of pipeline stages -1) and initiation interval =24 (as unpipelined). But it was mentioned that   the latency was 24 and initiation interval was 25.

latency and initiation interval and FP pipeline

Why is this?

Can anyone explain me? As I missing something

You can think latency as the time (# intervening clock cycles here) required to get a result from a producer instruction to a consumer instruction. For FP divider it is required 25 cycles and the unit is unpipelined. So, the #intervening CC = 24.
On the other hand, initiation interval is the duration of time that is required to issue two similar type instruction. As FP divider is unpipelined, so you can issue another FP divider after finishing the previous one which requires 25 clock cycles. If it was pipelined, I guess it would be 1.


Can anybody explain intuitively why quick sort need log(n) extra space and mergesort need n? I've searched on internet and everybody said it's stack space needed on recursion. I know log(n) extra space for quick sort happened when use in place, but still I don't get it. Anybody can explain intuitively why quick sort need log(n) extra space and mergesort need n? Thanks.

Quicksort: For quicksort, your intuition about recursion requiring O(log(n)) space is correct. Since quicksort calls itself on the order of log(n) times (in the average case, worst case number of calls is O(n)), at each recursive call a new stack frame of constant size must be allocated. Hence the O(log(n)) space complexity.

Mergesort: Since mergesort also calls itself on the order of log(n) times, why the O(n) space requirement? The extra space comes from the merge operation. Most implementations of merge use an auxiliary array with length equal to the length of the merged result, since in-place merges are very complicated. In other words, to merge two sorted arrays of length n/2, most merges will use an auxiliary array of length n. The final step of mergesort does exactly this merge, hence the O(n) space requirement.

To see exactly how the auxiliary array is used, check out this implementation of merge.

Summary: The key difference between the two lies in the space requirement of the operation performed at each recursive step. The partition step used in quicksort is an in-place operation, while merging usually requires an auxiliary array.


Limited sort: is this a well-known problem? I came up with a problem, and I'm having trouble finding existing work on it. I'm not sure if there is a polynomial-time solution for it. Is this a well-known problem (or equivalent to one)?

We define a function limited_sort(input, n) -> output that takes an array of comparable elements input and an integer n and returns output which is a permutation of input such that that no element in output is more than n spaces from its original position in input. output is the permutation that has the lowest number of inversions (subsequent elements a, b such that a > b) out of all such permutations (if there are multiple minimal permutations, output is the lexicographically lowest of them).

For example, limited_sort([4, 1, 0, 2, 3], 2) returns [0, 1, 4, 2, 3], which has 1 inversion (4, 2). 0 inversions is not possible because you'd have to fully sort the list, and the element "4" would move 4 spaces which is not allowed. [4, 0, 1, 2, 3] is also valid with 1 inversion but it's lexicographically higher than [0, 1, 4, 2, 3].

Is there a solution that is polynomial-time in both n and L (the length of input)?

I think absolutely minimising the number of inversions makes this very hard. If you just say "I want an array that is a bit better sorted, without moving any item by more than n positions": Fill a heap with the first n+1 array elements. Then remove the smallest element in the heap and put it into the first array position, unless there is an array element in the heap that would end up moving too far. Add the next array element to the heap and repeat. Obviously stop adding elements to the heap when you run out of elements.

This will find [0, 1, 4, 2, 3] in your example.


Intersection of Decision Tree Boundaries in Higher Dimensions I have trained two binary decision tree classifiers with splits in $\mathbb{R}^4$. Same data, but from two different patches.  Now, I want to find the exact intervals where the two trees disagree.
The splits are along the lines of:
\begin{align*}
& (x_1 > 0.35592521727085114) \wedge  (x_3 \leq-0.13628841191530228) \implies 0, \\
& \vdots \\
& (x_3 \leq -0.013720870949327946) \wedge (x_1 > 0.35592521727085114) \wedge (x_3 > -0.13628841191530228) \implies1. \\
\end{align*}
($x_2$ and $x_4$ are allowed to live anywhere between their absolute bounds.)
Any advice on how to approach this?  I've read some material on interval trees, and theoretically at least I can see how they might be expanded to higher dimensions, but I'm wondering if someone out there has experience with a particular tree variant, or other data-structure that would be appropriate in this case.
Help very much appreciated.

Yuval Filmus has articulated an elegant solution, which I'll expand on.
Given a leaf of a decision tree, it is easy to characterize the set of values of $x$ that reach that leaf.  Namely, you take the conjunction of all the conditions along the path from the root to the leaf.  For trees of the form you list, this will have the form $[\ell_1,u_1] \times \cdots \times [\ell_4,u_4]$, i.e., the set of all $x$ such that $\ell_1 \le x_1 \le u_1 \land \cdots \land \ell_4 \le x_4 \le u_4$, where you can explicitly compute $\ell_1,\dots,\ell_4,u_1,\dots,u_4$.
Now apply the following algorithm:

For each pair of leaves, with one leaf in the first tree and the other leaf in the second tree, such that the two leaves lead to different classifications:

Compute the set of values $x$ that reach the first leaf, the set of values $x$ that reach the second leaf, and compute their intersection.  Output the intersection (this is one set of points where the decision trees differ).

The union (i.e., disjunction) of all of those outputs will be the complete set of points where the two trees give a different decision.

It is possible to come up with algorithms that might be faster; however, I'm not sure whether they will lead to a significant improvement in higher dimensions.
One approach is to construct a new tree via a "product construction".  Thus, each node in the new tree is a pair $(u,v)$, where $u$ is a node in your first tree and $v$ is a node in your second tree.  The root of the tree is $(r_1,r_2)$, where $r_1$ is the root of your first tree and $r_2$ is the root of your second tree.  You can build the new tree top-down, starting from $(r_1,r_2)$, then splitting using the condition at one of these two nodes ($r_1$ or $r_2$).  As you build the tree, keep track of the set of values that can reach each new node $(u,v)$.  If this set is empty, you can prune it and don't need to explore any of its children.  This might reduce the number of nodes you need to expand.  In the worst case, there is no speedup, but in practice, it might help a little.

It gets more interesting if each classifier is an ensemble/forest of trees; then the best solution would probably be to use a SMT solver.


Closed form for the recurrence T(n) = T(n-1) + n² Given the following recurrence:

$$ T(n) = T(n-1) + n^2$$

How can I prove it to be $O(n^3)$ with the substitution method? The $O(n^3)$ guess derives from the fact that at every step of the recursion we pay $n^2$ and we have $n$ steps of recursion therefore having: $n \times n^2 = n^3$.

I would even expect this to be $\Theta(n^3)$, but I can't even prove $O(n^3)$.

I tried with the guess:

$$ T(n) \leq n^3 + n^2 \cdot c_1 + n \cdot c_2 + c_3 $$

but that yields:

$$ T(n) \leq n^3 + n^2 \cdot (3 + c_1) + n \cdot (c_2 - 2c_1 -1) + (c_1 - 1 - c_2 + c_3) $$

which yields:

$c_1 = c_1 + 3$
$c_2 = c_2 - 2c_1 - 1$
$c_3 = c_1 - 1 - c_2 + c_3$

But even from the very first ($c_1 = c_1 + 3$) we find that no $c_1$, $c_2$ or $c_3$ satisfy the equations.

What did I do wrong?


Difference between pattern matching and pattern searching in terms of DFA/Regex E.g.

Matching Problem The DFA of regex good is like a chain.

match:     "good"
not match: "people do not give good comments are not good people"

Searching Problem The DFA used in searching regex good could be:

1 matching:  "good"
2 matchings: "people do not give good comments are not good people"

Here are the questions:

In the above two problems, it seems the searching problem's DFA is the matching problem's DFA plus some backedges and an additional state (here state 0). Is this the difference in general?
What is the regex of searching problem in this case?

This is true in general, in a way.
Consider a regex $r$. You can construct a DFA (or NFA) for the matching problem. Denote this NFA by $A$.

To solve the searching problem, you can proceed in several ways.
First, you can just solve the matching problem for the regex $\Sigma^*\cdot r\cdot \Sigma^*$.

Alternatively, you can construct an equivalent NFA for the latter regex. The form of such an NFA would be an initial state that guesses when $r$ starts (at which point there is a transition to the initial states of $A$), and every accepting state of $A$ moves to an accepting sink.

This NFA can be thought of as a generalization of the situation you describe. Indeed, when you determinize it, the equivalent DFA essentially tracks $r$, and whenever it fails the DFA "resets". This is not exact, since it strongly depends on $r$.

When $A$ is a chain, then indeed determinizing the NFA yields a DFA that follows the chain, and whenever there is a "mistake" (that is, $r$ is not met), it resets to the initial state. However, it could be that resetting might not go as far as the initial state. For example, when searching for $aba$, if you see $aa$, then the second $a$ should not reset all the way back, but rather to the second state, since the second $a$ may be the start of the regex's occurrence.


Proof of the master thorem case with floors and b = 2 This question is related to my previous one.

Let the following recurrence relation be given: $T(n)=aT(\lfloor n/b \rfloor)+f(n)$ where $a\geq 1, b > 1$  and $f(n) = \Theta(n^{\log_ba})$. Then $T(n) = n^{\log_ba} + \sum_{j=0}^{\lfloor \log_b n \rfloor - 1} a^{j}f(n_j) = n^{\log_ba} + g(n)$. It should be proved that $g(n) = \Omega(n^{\log_ba}logn)$.

It's seems not to be a difficult problem as there is the proof of the similar one (for the upper bound and a presence of the ceiling operation in recursive calls) in the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein. But I found it becomes more difficult to deal with if $b=2$:

$n_j = \begin{cases}
n,  & \text{if j = 0} \\
\lfloor n_{j-1}/b \rfloor, & \text{if j > 0}
\end{cases}$

$n_j \geq n/b^{j} - \sum_{i=0}^{j-1}1/b^{i} \geq n/b^{j} - \sum_{i=0}^{\infty}1/b^{i} = n/b^{j} - b/(b-1)$

By condtition, there is such constant $c$ that

$g(n) \geq$

$c \sum_{j=0}^{\lfloor \log_b n \rfloor - 1}a^{j}(\frac{n}{b^{j}} - \frac{b}{b-1})^{log_ba} =$

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{j}}{n}\frac{b}{b-1})^{log_ba} \geq$   //where $\frac{b^{j}}{n} \le 1$

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{\lfloor log_bn \lfloor -1  }}{n}\frac{b}{b-1})^{log_ba} = $

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{\lfloor log_bn \lfloor }}{n}\frac{1}{b-1})^{log_ba} \geq$

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{1}{b-1})^{log_ba}$

Note iff $b = 2$ than $(1-\frac{1}{b-1})^{log_ba} = 0$ and can not be denoted as an allowable constant in terms of $\Omega$ (it must be a positive one).

I tried to prove that particular case in another way, if $n_j \geq \frac{n}{2^{j}} - (2 - \frac{1}{2^{j-1}})$ (it is the sum of the geometric progression without the limit) but finally failed because of the same issue.

In fact, let $b=1.5$, we will have $(1-\frac{1}{b-1})<0$, in which case $(1-\frac{1}{b-1})^{\log_ba}$ does not even make much sense!

The problem can be traced to when the following too-relaxing relaxation was made.

$$1-\frac{b^{j}}{n}\frac{b}{b-1} \geq 1-\frac{b^{\lfloor \log_bn \rfloor -1  }}{n}\frac{b}{b-1}$$

Can we find $\Theta(\log n)$ times when the left side is greater than, for example, $\frac12$? That should be enough to generate the factor $\log n$ needed.

Let us solve the following equation for the index $j$.
$$1-\frac{b^{j}}{n}\frac{b}{b-1} \gt \frac12$$
We get
$$j \lt \log_b\left(\frac{n(b-1)}{2b}\right)=\log_bn-\log_b\frac{2b}{b-1}=\frac{\log n}{\log b}-c_0$$
where constant $c_0=\log_b\frac{2b}{b-1}$.

The above should be enough to set you moving for a complete proof, although there might be a couple of other minor technicalities ahead.


Dominance Law in Boolean Algebra The dominance law states that x + 1 = 1

If we go by that logic, does that mean that x' + 1 = 1?

Please just tell me if it's a yes(as I think that this is the answer but I just want to clear my doubts) and maybe provide a little explanation if it's a no.

Thanks!

If $x+1=1$ then, substituting $x'$ for $x$, we deduce that $x'+1=1$.

In other words, your claim follows from the fact that $x'$ has the same "type" as $x$.


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

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

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

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

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

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

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

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


Priority queue with both decrease-key and increase-key operations A Fibonnaci Heap supports the following operations:

insert(key, data) : adds a new element to the data structure
find-min() : returns a pointer to the element with minimum key
delete-min() : removes the element with minimum key
delete(node) : deletes the element pointed to by node
decrease-key(node) : decreases the key of the element pointed to by node

All non-delete operations are $O(1)$ (amortized) time, and the delete operations are $O(\log n)$ amortized time.

Are there any implementations of a priority queue which  also supportincrease-key(node) in $O(1)$ (amortized) time?

Assume you have a priority queue that has $O(1)$ find-min, increase-key, and insert. Then the following is a sorting algorithm that takes $O(n)$ time:

vector<T>
fast_sort(const vector<T> & in) {
  vector<T> ans;
  pq<T> out;
  for (auto x : in) {
    out.insert(x);
  }
  for(auto x : in) {
    ans.push_back(*out.find_min());
    out.increase_key(out.find_min(), infinity);
  }
  return ans;
}


Question for "Only if" part for the theorem "A language is Turing-recognizable iff some enumerator enumerates it." I am trying to prove the theorem

  A language is Turing-recognizable iff some enumerator enumerates it.

I proved the "if" part, but I have no idea of proving the "only if" part, so I searched a proof for the "only if" part of this theorem. In the proof that I found,  it says

  Let $\sum$ be the alphabet of the Turing machine $M$, and let $s_1$, $s_2$, ... be a list of all possible strings of $\sum^{*}$. We define the enumerator $E$ as follows:
  1. Run $M$ for $i$ steps on each input $s_1$, $s_2$, ... , $s_i$.
  2. If any computation of $M$ accepts, print out the accepted string.

In this proof, I can't understand why do we need to run $M$ for only $i$ steps. I think the number of simulation steps may not be enough to simulate strings. Is it guaranteed that simulating $M$ finishes in $i$ steps?

A language is Turing-recognizable (or Recursively enumerable) iff there exists a Turing Machine which will enumerate all valid strings of the language.

What you probably miss in the above proof is the fact that $i$ can take any value ... when we say $i$ steps, we can mean $10$, $100$, $100000$, $\infty$ steps.
Basically $i$ is an index that indicates the number of words in the language; the enumerator $E$ could very well run forever (if the language has an  infinite number of strings).


r-regular graph and hamiltonian path I am having some issues proving a problem I am working on. I have been sketching out examples but the proof is not jumping out at me.

Question:
Let $G = (V,E)$ be an undirected $r$-regular graph (that is each vertex has a degree of $r$) for some $0 < r < n$, where $|V| = n > 1$. Prove that either $G$ or its complement $G^*$ has a hamiltonian path.

Now the reason it's asking for $G$ or $G^*$ is because if it's not a connected undirected graph then taking the complement will make it connected.

So lets assume that it's a connected $r$-regular graph. We start at a vertex $v$. From this vertex we can visit up to $r$ adjacent vertices. So we visit one of them, say $u$, and from there we have $r-1$ vertices to choose from because we do not want to go back to vertex $v$.

Now I am trying to formulate a proof by going from vertex to vertex until all vertices are visited exactly once (hamiltonian path). But I do not see how to formulate the proof. Somehow each new vertex I visit will always have an uninformed neighbour until I reach the final vertex on the path.

Am I on the right track?

You are underselling the "G or G*" part. This suggests a proof of the form:

"assume G isn't Hamiltonian ... prove G* must be". So try that route.

To give a further hint, I remind you of the Dirac theorem:

If a connected graph G has n >= 3 vertices and the degree of each vertex is at least n/2, then G has a Hamiltonian cycle (if it has a cycle, obviously it also has a path, you just remove an edge from the cycle).
Additionally, an n-vertex r-regular graph with r >= n/2 must be connected (assume it is not connected - what is the minimum number of vertices each connected component must have? Can there be more than 1 such component?)

I think these should give you the idea how to prove it for n >= 3.

Then it just remains to prove it for n = 2, which is trivial (the only reason it isn't included in above theorem is that it only has a path, not a cycle).

Note: because I am not sure a complement is even defined on a non-simple graph, I am assuming G is simple. But if it wasn't, the statement-to-prove couldn't be true, even if you defined a complement in any way that makes sense - what would be the complement of this graph, and how could either have a Hamiltonian path:


How to determine minimum word length of regular language Given a regular language $L$ and a regular expression $r$ with $L=L(r)$. Is it possible to determine the minimum length of words of $L(r)$ by the structure of $r$?

A straightforward example:

Let's say we have a regular expression $r=aac^*aa$, then $L(R) = \{aaaa, aacaa, aaccaa, \dots, aac^naa\}$. To determine the minimal length I would erase everything that is postfixed with $*$, leaving $r'=aaaa$. Now I would count the concatenations and add 1, which would yield in this example, not unsurprisingly, a minimum length of 4.

Is there a general approach to do this for more complex expressions?

Sidenote: I need to achieve this without the help of automata.

First, notice that you can easily eliminate $\emptyset$ for all regular expressions other than a regular expression describing the empty language. To do this, you use the following rewriting rules, which define an operator $E$ on regular expressions:

$E[\sigma] = \sigma$, $E[\epsilon] = \epsilon$, $E[\emptyset] = \emptyset$.
$E[r_1 r_2]$ is $\emptyset$ if one of $E[r_1],E[r_2]$ is $\emptyset$, and $E[r_1]E[r_2]$ otherwise.
$E[r_1 + r_2]$ is $E[r_1]$ if $E[r_2] = \emptyset$, $E[r_2]$ if $E[r_1] = \emptyset$, and $E[r_1] + E[r_2]$ otherwise.
$E[r^*] = \epsilon$ if $E[r] = \emptyset$, and $E[r]^*$ otherwise.

You can prove inductively that $E[r]$ either doesn't contain $\emptyset$, or is equal to $\emptyset$.

Applying these rewriting rules, we have either determined that the denotation of the regular expression is empty, or are given a regular expression without $\emptyset$. Now we define an operator $m$ which determines the length of the minimal word in an $\emptyset$-free regular expression:

$m(\sigma) = 1$, $m(\epsilon) = 0$.
$m(r_1r_2) = m(r_1) + m(r_2)$.
$m(r_1 + r_2) = \min(m(r_1),m(r_2))$.
$m(r^*) = 0$.

You can also implement both operators at once, by allowing $m$ to output $\infty$ (meaning that the language defined by the regular expression is empty):

$m(\sigma) = 1$, $m(\epsilon) = 0$, $m(\emptyset) = \infty$.
$m(r_1r_2) = m(r_1)+m(r_2)$, where $\infty + \ell = \ell + \infty = \infty$.
$m(r_1+r_2) = \min(m(r_1),m(r_2))$, where $\min(\infty,\ell) = \min(\ell,\infty) = \ell$.
$m(r^*) = 0$.


Time complexity of a precedence constrained selection problem I wonder if you have an idea over the time complexity of the following problem, or a problem similar to this one (generally a selection problem)

[Assuming operations on integers take O(1) time]

We are given a set $N$ of $n$ items, that are subject to general precedence constraints (a partial order $E$ on $N$). The problem could then be represented by an acyclic directed graph $G(N,E)$ where the nodes represent items and edges represent precedence constraints. Each item has a selection cost $c_i$ that may be positive, zero, or negative. The objective is to find a subset $S \subseteq N$ of items that is precedence feasible, i.e., $\forall i \in S:\{j \in N|(j,i) \in E\}\subset S$, and minimizes the total selection cost $F(S)=\sum_{i \in S}c_i$.

I tried to find a reduction from CLIQUE or 3-Dimensional Matching, but I couldn't.

Thank you in advance :)

If you flip the signs on your costs and reverse edge directions, this is the Closure Problem, also known as the Open-Pit Mining Problem, and it's actually solvable in polynomial time using a rather non-obvious transformation into maximum flow.

The algorithm is described in the Wikipedia page linked above.  Briefly, it involves setting the capacity of each edge to infinity, which has the effect that any minimum cut avoids all original graph edges in the forward direction (since any cut that included such an edge would have infinite flow), and adding a new edge to each vertex from one of two new vertices, $s$ (for positive-weight vertices) or $t$ (for negative-weight vertices).  The capacity of any $s$-$t$ cut magically works out to be a constant minus the total weight of vertices on one side of the cut, so minimising this (which can be done by a max-flow algorithm) maximises said total weight!


How do I test if a polygon is monotone with respect to a line? It's well known that monotone polygons play a crucial role in polygon triangulation.

  Definition: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice.

Given a line $L$ and a polygon $P$, is there an efficient algorithm to determine if a polygon $P$ is monotone with respect to $L$?

Hint: A generic simple polygon is monotone with respect to the $x$-axis if and only if it has exactly one vertex whose $x$-coordinate is smaller than its neighbors.  This observation immediately suggests an $O(n)$-time algorithm, at least if no edge of your polygon is vertical.

Spoilers ahoy:

  IsMonotone(X[0..n-1], Y[0..n-1])
    local_mins ← 0
    for i ← 0 to n-1
        if (X[i] < X[i+1 mod n]) and (X[i] < X[i-1 mod n])
            local_mins ← local_mins + 1
    return (local_mins = 1)

If you're worried that your polygon might have vertical edges, use the following subroutine in place of the comparison X[i] < X[j] to consistently break ties:

IsLess(X, i, j):
    return ((X[i] < X[j]) or (X[i] = X[j] and i < j))

Finally, if $L$ is some other line of the form $ax+by=c$, modify IsLess as follows:

IsLess(X, Y, i, j):
    Di ← a·X[i] + b·Y[i]
    Dj ← a·X[j] + b·Y[j]
    return ((Dj < Dj) or (Di = Dj and i < j))


Clarifying "operation" in the definition of data type A definition of data type I've seen is along the lines of "a set of values and a set of operations".

What exactly does an operation in this set comprise?

For instance, might an operation be considered as:

an identifier (e.g. integers have an operation, +)
an identifier with signature (e.g. + operates on two integers and results in an integer)
an identifier with signature and established behaviour (e.g. 1 + 2 = 3)
an identifier with signature and behaviour, together with some underlying implementation

or some other concept?

It sounds like you might be asking about an abstract data type.  If so, the answer is the third option: "an identifier with signature and established behaviour".

If you are asking about a data type, then I'm not sure there's a clear answer that applies to all type systems and all programming languages.  Syntactically, I think it falls closest to your second option: "an identifier with signature" -- the type checker doesn't know anything about the intended behavior.  However, in practice programmers might associate other things with a type: for instance, the type might indicate the intended meaning of the data, it might indicate the intended behavior of the operations, it might indicate how the data is represented or stored, and it might even encode other distinctions -- though many of these might not be checked by the compiler's type checking or might not be visible to the compiler.


In any finite simple graph with more than one vertex, there is at least one pair of vertices that have the same degree? Recently, I am reading the book [1]. I am trying to solve the following problem:

1.2 Pigeons and holes. Properly speaking, we should call our representation of Königsberg a multigraph, since some pairs of vertices are connected to each other by more than one edge. A simple graph is one in which there are no multiple edges, and no self-loops.
Show that in any finite simple graph with more than one vertex, there is at least one pair of vertices that have the same degree. Hint: if $n$ pigeons try to nest in $n - 1$ holes, at least one hole will contain more than one pigeon. This simple but important observation is called the pigeonhole principle.

The following is my attempt to solve the problem: Let $G$ be a finite simple graph that has $N_V$ vertices and $N_E$ edges. Because each edge connects two vertices, the number of total degrees is $2 N_E$. Let $d_i$ be the degree of the $i$th vertex for $i = 1, 2, ..., N_V$, then
$$\sum_{i = 1}^{N_V} d_i = 2 N_E. \tag{1}$$
On the other hand, we know
$$0 \leq d_i \leq N_V - 1. \tag{2}$$
When $d_i = 0$, it means that the $i$th vertex does not connect with any other vertices. A vertex can connect with at most $N_V - 1$ vertices.
Then I don't know how to continue. Could any one please tell me the correct solution? Thanks in advance.
Note: It is not my homework. I am just interested in solving the problem.
Reference:
[1] C. Moore and S. Mertens, The Nature of Computation, Oxford University Press, 2015.

This one is a bit tricky! Here is the idea. We would like to use the pigeonhole principle. However, there are $n$ vertices and $n$ possible degrees $0,\ldots,n-1$, so the pigeonhole principle allows the situation in which each degree appears exactly once. We can flatly rule it out for values of $n$ which are of the form $4m+2$ or $4m+3$ using the handshake lemma, which states that the sum of the degrees is even, but what about the general case?

It turns out that to solve the general case we don't even need the handshake lemma. The following observation suffices (and explains why we need $n>1$):

   If $n > 1$ then a graph cannot contain both a node of degree $0$ and a node of degree $n-1$.


Intuitive way to understand the triangle spectrum? Image on the top is in the time domain, image on the bottom is in the frequency domain.

Why do we see -2T and 2T on image of the time domain and why do we see -1/2T and 1/2T of the image in the frequency domain?

Suppose there is a sound with frequency 440Hz. How large is each period of this periodic signal? It must be (1/440)s. The same applies in your case.


Proving that Max Weighted Independent Set is in NP What I'm trying to do is to show a problem in NP can be reduced to the min weight vertex cover problem

I've chosen the max independent weight problem =
input: A graph G with weights on each vertex,
output: An independent set with the max total weight

Before reducing, I've tried to show that the max indep. weight problem is in NP (which is usually the first step in these reductions). I'm trying to construct a verification algorithm for this problem; but I'm stuck on trying to show that the verification algorithm can check if a certificate is the max indep. set in polynomial time.

Any guidance or comments would be greatly appreciated.
Thanks

The issue is with the version of the problem you are using. Note that as you define it, the output is required to be the maximum weight independent set, i.e. the optimum answer. $NP$ however is a class of decision problems, so the only valid outputs are Yes and No.

So if you want to show the problem is in $NP$ you first need to convert it to a decision problem:

  $k$-Weight Independent Set
  Input: A vertex weighted graph $G=(V,E,w)$ and an integer $k$.
  Question: Is the a set $V'\subset V$ such that $V'$ is an independent set and $\sum_{v\in V'} w(v) \geq k$?

It should be easier to see that this version is in $NP$. There is an optimization class - $NPO$ - that corresponds to $NP$, but the normal definition is that a problem is in $NPO$ if its decision variant is in $NP$ - so you're still in the position where you want to deal with the decision variant.


Could neural networks be considered metaheuristics? A metaheuristic is defined as

  a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem

So my question is if a neural net could be consider in that definition

The notion of a "metaheuristic" is not something with a precise formal definition.  Personally, a neural network isn't something I'd consider a metaheuristic; it doesn't seem quite like what we have in mind when we talk about metaheuristics.  But you can always use language however you like, as long as it is clear to others and doesn't cause confusion.


What's the name of this sorting(?) algorithm? Given the options of:

Red
Orange
Yellow
Green
Blue
Violet

You want to find your favorite color by comparing all pairs to each other, like so:
Red vs...

Red vs Orange = Orange
Red vs Yellow = Red
Red vs Green = Red
Red vs Blue = Red
Red vs Violet = Red

Orange vs...

Orange vs Yellow = Orange
Orange vs Green = Orange
Orange vs Blue = Orange
Orange vs Violet = Orange

Yellow vs...

Yellow vs Green = Green
Yellow vs Blue = Yellow
Yellow vs Violet = Yellow

Green vs...

Green vs Blue = Green
Green vs Violet = Green

Blue vs...

Blue vs Violet = Violet

In the end you'll find your "most preferred". Not sure if you get a full order of preference.
What's the name of this...thing?
Also as D.W. described, I believe it's solved by which color won most often. So in the example above:

Orange = 5
Red = 4
Green = 3
Yellow = 2
Violet = 1
Blue = 0

If we can assume that there is a total order on all colors: to find the largest element, there is a straightforward $O(n)$-time algorithm to find it: you scan through all colors, keep tracking of the largest element seen so far:

Set $m$ to the first color.
For each other color $c$:

Set $m := \max(m,c)$.

(Here $\max$ refers to the larger of the two colors, i.e., whichever is more preferred.) There is no need to "sort" all of the colors to find the largest (most favorite) color.
Alternative, suppose we cannot assume the colors are totally ordered, and the order is a partial order.  Then you'd need to specify what is meant by "most favorite" color.  One possible definition is a maximal color, i.e., one where no other color is more preferred.  (Note that there may be multiple such colors.)  If so, you can again find it via the same linear scan (if two elements are incomparable, you stick with the current element).


What are some decidable problems which cannot be solved in real life(due to time and memory constraints)? The first line of Sipser book for the Chapter- 'Time complexity', says that:

Even when a problem is decidable and thus computationally solvable in principle, it may not be solvable in practice if the solution requires an inordinate amount of time or memory.

My question is, yes we do have limited space and time, so the above statement makes the whole P and PSPACE concept as vague, right? If it so, what are these problems? Are such huge inputs acceptable in practice?

Given an integer k, are there integers (positive or negative) x, y, z with an absolute value ≤ $10^{1000}$ such that $x^3 + y^3 + z^3 = k$?

It is believed that without the limit on the absolute values the answer is "Yes" unless $k \equiv 4 \mod 9$ or $k \equiv 5 \mod 9$. On the other hand, solutions are so rare that most likely solutions for some values k cannot be found in the lifetime of the universe.

And both the inputs, and the space needed for a computation, are tiny. The limitation on the size of x, y, z makes it decidable.


Show that PTIME and PSPACE is closed under Klenee star How to show that PSPACE and PTIME are closed under Kleene star ?  I can only show that NP is closed, but it is easy because we can use non-determinism to guess partition of word. In these two cases I don't have idea how to attack it.

Suppose you are given a language $L$ in one of these complexity classes, and you want to decide $L^*$ in the same complexity class. On input $x_1 \ldots x_n$ (where the $x_i$ are bits), use dynamic programming to find out which substrings $x_i x_{i+1} \ldots x_j$ belong to $L^*$. Since there are only $O(n^2)$ such substrings, this will only cause a polynomial blow-up in the resources used.


The difference between a bit and a Qubit Ok, I have done a lot of research on Quantum computers. I understand that they are possibly the future of computers and may be commonplace in approximately 30-50 years time.

I know that a Binary is either 0 or 1, but a Qubit can be 0 or 1. But what I don't understand is how it can be anything other then 0 or 1. Surely a computer can only understand on and off, despite however fast it may be?

Probably the easiest analogy is to probabilities. If your computer can flip fair coins, you can think of each coin being in state Tails with probability 1/2 and in state Heads with probability half. So it's appropriate to think of a coin not as a bit but as a vector of two elements $(p_T, p_H)$, where $p_T$ is the probability of tails, $p_H$ is the probability of heads and we have that $p_T \geq 0$, $p_H \geq 0$, and $p_T + p_H = 1$. Once we sample a coin its state "collapses" to either tails or heads.

Just about the same happens with qubits. You can also think of quibit as being "in between" two states. It's also easiest to think of qubit not as a bit but as a vector of two elements $(q_0, q_1)$. Now, however, we allo $q_0$ and $q_1$ to be negative, and even further, to be any two complex numbers, as long as $|q_0|^2 + |q_1|^2 = 1$. Just as with sampling coins, once you measure a qubit, it collapses to either $0$ or $1$, and in fact you get $0$ with probability $|q_0|^2$ and $1$ with probability $|q_1|^2$. However, and this is the crucial part, these quantum probabilities can be made to cancel each other because they take negative values; this cannot happen with classical probability. This is the power of qubits.

BTW these complex valued quantities describe amplitudes and are related to the wave-particle duality, i.e. the discovery that particles in fact behave as waves, until you measure them, and then they behave as particles. The cancelation I am talking about is in fact interference between waves. So another answer to your question is that a qubit is not a discrete object that's either in one state or not, it's a wave..until  you measure it.


Algorithm to find smallest number divisible by N with sum of digits as N Problem:

  Given $N$, find the smallest number divisible by $N$ whose sum of digits is equal $N$.

For example:

$n = 1$, answer is $1$
$n = 10$, answer is $190$

There is some dynamic programming algorithm, but I can't find it.
It is sequence https://oeis.org/A002998.

Assuming that "number" means "positive integer", every number divisible by $N$ must be at least $N$. Conversely, $N$ has the same digit sum as itself. Therefore the answer is simply $N$, as your two examples demonstrate.


High Dimensional Spaces for Images Can anyone explain why pictures are not considered 2D, but rather high dimensional? Especially with regards to CV and AI.

From one perspective, a picture is a 2D image, because it has height and width.

But from a machine learning perspective, we can think of a picture as a point in a high-dimensional space.  In particular, suppose we have a greyscale picture that is $m\times n$ pixels, i.e., $m$ pixels wide and $n$ pixels high.  Then there are a total of $mn$ pixels in the image.  Each pixel has a greyscale intensity, which we can think of as a real number in the interval $[0,1]$.  Therefore, we can think of the picture as being a collection of $mn$ real numbers.  In other words, the picture can be treated as a $mn$-dimensional vector -- as an element of $\mathbb{R}^{mn}$.  Thus, any particular picture can be thought of as an element of a high-dimensional space.

The latter perspective arises natural for some machine learning approaches to computer vision, e.g., where we feed the pixels of the image into the machine learning algorithm, where each pixel value is treated as a separate pixel.

(A color image can be thought of as an element of $\mathbb{R}^{3mn}$: for each pixel, we have three numbers, corresponding to the intensity in the red, green, and blue channels.)


Where/when did Stephen Kleene first define the Kleene closure/star? I'm working on a paper and would like to review the origins of Kleene's closure. I am unable to find any article of Kleene's that has the original definition of the Kleene closure.

Is there a paper by Kleene in which he first defines the Kleene closure?

Kleene's classic paper on finite automata and regular expressions is

  Kleene, Stephen C.: "Representation of Events in Nerve Nets and Finite Automata". In Shannon, Claude E.; McCarthy, John. Automata Studies, Princeton University Press. pp. 3–42., 1956.

There seems to be a scan or recreation of that version of the paper at: http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf.

But, as pointed out by @HendrickJan, the work seems to have been done about 5 years earlier.  The article starts with a note that says that "the material ... is drawn from Project RAND Research Memorandum RM-704 (15 Dec 1951, 101 pages) ... used by permission of the RAND Corporation ... supported by the RAND Corporation during the summer of 1951."  A scan of the RAND research memorandum is available for free from the RAND website: http://www.rand.org/pubs/research_memoranda/RM704.html.

"Regular events" are defined in Section 7 of both papers.  (page 46 of the 1951 memorandum and page 23 of the 1956 paper).  Interestingly, Kleene defines $*$, the closure operator, as a binary operator, rather than a unary operator as we do today.  This enables Kleene to avoid dealing with empty strings.  $E*F$ means the same thing it does today: "0 or more instances of E followed by F" but there is no way to say $E^*$ and have it include the empty string.


Proving that L is not regular by showing that $\equiv_L$ has infinite index Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has finite index
We show: $\equiv_L$ has infinte equivalence classes.
$a^{3^i}$ $\not\equiv$ $a^{3^{i+k}}$, $k>0$
-> equivalence classes: [a], [aaa], [$a^3$]...
Every $a^{3^i}$ is a different equivalence class.
Therefore $\equiv_L$ has an infinite amount of equivalence classes $\rightarrow$ L is not regular. qed.

How to show that the classes are different?

Let me prove a stronger claim: every two words over $\{a\}$ are inequivalent with respect to your language. What this means is that for every $i \neq j$, there is a word $w \in a^*$ such that either $a^i w \in L$ and $a^j w \notin L$, or vice versa. Since $w \in a^*$, in fact $w = a^k$ for some $k$, and so we need to prove the following:

  If $i \neq j$ are natural numbers then there exists a natural number $k$ such that exactly one of $i+k,j+k$ is a power of 3.

Let $a_i$ be the smallest power of 3 which is at least $i$, and define $a_j$ similarly. If $a_i \neq a_j$, say $a_i < a_j$, then we can take $k = a_i$. So suppose $a_i = a_j = a$. Without loss of generality, $i < j$, and so $i+a < j+a$. The next power of 3 after $i+a$ is $3(i+a)$, and after $j+a$ is $3(j+a)$. Let $k = 2i+3a$. Then $i + k$ is a power of 3 by definition, but $j+a < j + k < 3(j+a)$ is not a power of 3.


Anyone knows an algorithm that finds minimum distance for all permutations? Let $A$ and $B$ be two finite sets of the same size $n$. Let $P(A),P(B)$ be the set of all permutations of $A,B$ respectively. A distance function $d(a,b)$ is defined for any $a\in P(A),b\in P(B)$. We want to find $\min \{d(a,b):a\in P(A), b\in P(B)\}$ (note: $d$ is fixed).
For example, suppose we have two sets $\{1,2\}$ and $\{3,4\}$, and the distance $d$ is Euclidean distance, then all possible distance values are

$d((1,2),(3,4)) = \sqrt8$
$d((1,2),(4,3))=\sqrt {10}$
$d((2,1),(3,4)) = \sqrt{10}$
$d((2,1),(4,3)) = \sqrt{8}$

So the minimum value is $\sqrt 8$.
I think this is a very common problem so there should be some known algorithm out there. Anyone knows an efficient algorithm to solve this problem and help provide the name or reference? Thank you!

Surprisingly, if the distance is $L_p$, or the $p$-norm induced metric, then you simply sort $A$ and $B$ respectively, and then compute their distance, and that distance will be guaranteed minimal over all permutations. That is time complexity of $O(n\log n)$ and I believe it is the most efficient one.

The key proof is done in https://math.stackexchange.com/questions/1984686/is-x-1-y-2px-2-y-1p-ge-x-1-y-1px-2-y-2p-for-any-0-le-x-1-le.

Sometimes, before setting out to find an "efficient" algorithm, it might be a good practice to first think of proving the "greedy" algorithm is not right; because if the greedy indeed works, all efforts to search for the "efficient" algorithm will be in vain.


Structure for getting $| \{ a,b \} \subset S : a+b \le d|$ in O(1) I am struggling with exercise from the old algorithmic exam:
$d$ is const for the whole structure.
Propose a structure for which you can do:

Init(S) //called only 1 time
Insert(x, S)::  $ S := S \cup \{x\}$ in O(log(|S|)
Delete(x, S):: $ S := S \setminus \{x\}$ in O(log(|S|)
Get(S) = $| \{ a,b \} \subset S : a+b \le d|$  in O(1)

I am trying to that with AVL Tree with additional members like number of nodes such that $v.value+u.value \le d$.
 Could somebody give me some hint?

It is on the right direction to try some kind of tree augmented with a global counter that stores the number of all unordered pairs of nodes $\{u,v\}$ such that $v.value+u.value \le d$.

The kind of tree you are looking for is a balanced (binary) search tree. Being balanced such as an AVL tree, it supports insertion, deletion and lookup of a number with $O(\log|S|)$ time.  Being sorted as well, it can also update that global counter in $O(\log|S|)$ time if we can maintain some extra information on each node of the tree.

What should be those extra information? One approach is that each node $v$
will have a member $lcount$ that stores the number of nodes in its left subtree as well as a member $rcount$ that stores the number of nodes in its right subtree.

To simplify the explanation, let us use AVL tree. We will assume all values are distinct; otherwise, we can add a duplicity counter to each node.

Each insertion or deletion involves at most two tree rotations. Each rotation changes the edges between at most several nodes. So we can update all $lcount$ and $rcount$ in $O(\log|S|)$ time.

Before the insertion of node $n$, we should compute the number of nodes whose values are not greater than $d - n.value$, which is one plus the number of nodes to the left of the node $m$, whose value is the greatest but no greater than $d-n.value$. With the insertion of $n$, we will keep the global_counter intact if there is no such node $m$. Otherwise, letting $ancestor$ be $m$, we will do the following.

while ancestor is not null:
  if anc.value < m.value:
    global_counter := global_counter + ancestor.lcount + 1
  ancestor := ancestor.parent

The case of deletion is similar to the case of insertion.

Further explanation will be omitted.

Thanks to OP, who contributed to this answer.


Disproving well-quasi-order by providing an infinite anti-chain I am currently studying the theory behind Well-Quasi-Orders. However I am having some issues in understanding how an infinite   anti-chain can be produced to disprove the claim that a partial order $P$ is a w.q.o.

In particular I am wondering whether it is  logically sound to   present  as proof not the infinite anti-chain  but rather an algorithm to produce it.

More specifically, I've been trying to solve  an exercise from the following lecture
which asks whether the class of $P_{3}\text{-free}$ graphs is a w.q.o or not on the induced subgraph operation $\leq_{i}$

I've proved that said class contains unions of  cliques and defined an ordering of this set as follows  $P=\lbrace G_{0},G_{1},G_{2},.... \rbrace$ with $G_{i}$ representing all  $P_{3}\text{-free}$ graphs on $i$ vertices  (and graphs in $G_{i}$  being  represented in a  touple-like alpharithmetic form $(a_{1},....,a_{i})$ such that $a_{1} \leq a_{2} \leq.... \leq a_{i}$ to avoid repetitions and $\sum_{j=1}^{i} a_{j}=i$ to define  an order. For example $(0,0,2,2)$ $\in G_{4}$  encodes the graph with two disconnected $P_{2}$ components.

I have defined an algorithm $B$ that produces an anti-chain that grows bigger and bigger at each step

The algorithm uses gadgets  defined as $B_{a,c}$ which  represent the graph  with $c+1$ connected components, the first $c$ of which are $K_{1}$(i.e a sole vertice) and the last component representing $K_{a}$

The steps of my algorithm are the following:

Define $L$ as the sequence
Add $B_{a,0}$ to $L$    ($a$ any number $>$ 0)
repeat $\infty$ times:

4.Replace each  item  $B_{a,c} \in L$ by $B_{a^{'}=a+1 + 10^{6},c}$ and produce $L^{'}$  this way.

5.Let $X=B_{a^{'},c}$ be the graph with the maximum $c$  amongst those in $L^{'}$

6.Add to $L=L^{'}$ the graph $B_{a^{'}-2,c+1}$

Certainly, this algorithm does create an   anti-chain( in each step I create a graph with more connected components yet less  vertices). However I am not sure that such  a technique is valid for disproving w.q.o  on the infinite anti-thesis claim because of the fact that it works on a step by step basis.

Any help is appreciated. Thank you very much!

Your algorithm produces an infinite sequence of antichains whose size is unbounded. However, it doesn't produce a single antichain of infinite size.

It is perfectly fine to specify an infinite chain by giving an algorithm that enumerates its members, and even more complicated constructions are possible (e.g. the priority method). However, the end result of the construction should be a single infinite chain rather than a sequence of antichains of unbounded size.

I suggest taking a look at Higman's lemma.