$\omega$-regular expression to LTL Is there any systematic (algorithmic) method to convert an $\omega$-regular expression like

$
(a^∗)(b)(b^∗)(a^∗)(c^\omega)
$

to an LTL property?

LTL is less expressive than $\omega$-regular expressions. For example, the expression
$$((a+b)b)^\omega$$
i.e. "there is $b$ in all the even places"
cannot be expressed in LTL.

In addition, observe that checking whether an $\omega$ regular expression is expressible in LTL is harder than checking universality, which is PSPACE hard.

However, there are ways to tackle this problem. You can start here for a reference.


White-space and comment by lexical analyzer Lexical Analyzer mostly deletes comments and white-spaces. One example where I think Lexical Analyzer might not be discarding white-spaces is in Python language, as indentation has a important role in python. But I can't think of practical example where comments are/should be kept by Lexical Analyzer? Is there any such example you can think of?

White-space and comments can contain valuable information.

For white-space, you can look at layout sensitive languages, like Python or Haskell. I'm not sure how their lexers work, but off the top of my head I would store an indentation level, not the actual white-space.

For comments, it can be useful to store these if you want to generate documentation from Javadoc-style comments. For Javadoc, the parameter types do not have to be specified in the docblock (unlike PHPDoc, for instance). This means that a documentation generator would have to look at both the comments and the method header (everything before {). For the latter the lexer can be used, for the former it cannot (presuming the lexer removes comments).

I'm note sure how Javadoc-based documentation generators work, so perhaps the above is inaccurate, but the general idea is correct. I'm working on the Cloogle project, a Clean function search engine similar to Haskell's Hoogle. We hook into the Clean compiler to parse function types from all standard libraries. It would be nice if we could show comments around the definition as well, but the lexer removes this information. So, if we want to display comments, we have to adapt the compiler's frontend, or write a simplistic program that finds comments around some function, without lexing everything. If the lexer and parser would store comments, we would have a much more elegant solution.


Regular expression for strings not starting with 10 How can I construct a regular expression for the language over $\{0,1\}$ which is the complement of the language represented by the regular expression $10(0+1)^*$?

If a word doesn't start with $10$, then either it starts with some other combination of two letters, or it is shorter than two letters. All in all, we get the following regular expression for your language:
$$
\epsilon + 0 + 1 + (00+01+11)(0+1)^*.
$$


If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular? Say, $L \subseteq \{0\}^*$. Then how can we prove that $L^*$ is regular?

If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular.
Also I have noticed that, for $L = \{0^p \mid p \text{ is a prime}\}$, $L$ is not regular, $L \subseteq \{0\}^*$ and $L^*$ is regular.

But how to show this for any subset $L$ of $\{0\}^*$ ?

Assume that $L$ contains two words $w_1$ and $w_2$ such that the lengths of these words, $|w_1|$ and $|w_2|$, have no factors in common. Then, we have that the longest word that cannot be formed by concatenating these words has length $(|w_1|-1)(|w_2|-1) - 1$ (Frobenius number). That is to say, if there are words in the language whose lengths don't have a common factor, then all words of a certain minimal length are in the language $L^*$. It's easy to see this is regular since, of necessity, there are a finite number of equivalence classes under the Myhill-Nerode indistinguishability relation.

What if the lengths of all words in $L$ share a common factor? Well, It's not hard to see that in such cases, $L^*$ is also regular. Simply note that instead of all words whose lengths are greater than some minimal length being in $L^*$, it will instead be true that all words whose lengths are a multiple of the GCD of word lengths will be in $L^*$, and no words whose lengths aren't multiples of this GCD will be, and since $(L^k)^*$ is regular for any integer $k$, $L^*$ is also regular.

This is pretty informal, but everything you need to formalize this should be here.


Is there any problem that is R-complete and RE-complete R-complete, i.e. it is an analogue to all recursive language can be reduced to that problem and also recursive? Or is there a really such definition?

RE-complete is described on wikipedia. But what kind of reductions is used? Since we are already out of the set R, does it still make sense to define by many-one reduction?

Wikipedia hints at the definition of RE-complete. A language $A$ is RE-complete if for every r.e. language $L$ there is a computable reduction $f$ such that $x \in L$ iff $f(x) \in A$. There are two features of this definition:

We consider many-one reductions. This allows us to distinguish RE-complete problems from coRE-complete problems.
We allow any computable reduction. This is the strongest canonical class of reductions that still makes sense, since R is a proper subset of RE.

Both of these features are shared by the definition of NP-completeness.

As for R-completeness, I am not aware of any such definition, and I don't expect one. Indeed, the class of reductions allowed has to be smaller than all computable functions, since otherwise the definition trivializes (all nontrivial computable languages would be R-complete). Suppose for definiteness that we consider reductions running in time $t_1(n)$, and let $L$ be some R-complete problem with respect to such many-one reductions. Then $L$ runs in time $t_2(n)$, and so we would get that all languages in $R$ can be computed in time $t_1(n) + t_2(t_1(n))$, which clearly isn't the case. The same kind of argument rules out oracle reductions and space-bounded reductions.


Can I assume that a percentage of the time can be parallelized? I study computer science and hardware. Some problem are about parallel computing and applied Amdahl's law. For instance, some calculation is that the sequential part of a program takes x seconds and the parallel part takes y-x seconds. Can I then safely assume that it is the same percentage of the time that is parallel for different number of CPU:s or will that vary with different number of CPU:s?

You can never assume anything.

There are plenty of cases where your work, or a percentage of your work, can be split up into k independent tasks. If you have k processors, then each one can handle one task. If you have k+1 processors, then one will be unused. So it's not just a matter of "percentage of work that can be parallelised", it's also a a matter of "how many parallel tasks can be performed".

There are plenty of cases where work can be parallelised, but work needs to be done to prepare for this. Let's say it takes time t to prepare for one parallel execution, independent of the amount of work. So with two processors, that preparation takes 2t. With 100 processors, it takes 100t. If the amount of work is fixed, there will be a point where more processors add more preparation time than the savings you get.

There are plenty of cases where there is a simple sequential solution, and a more complex and slower parallel solution. The total time using one processor and the sequential solution may be x. To use k processors may save y of the sequential time, but add f (k) sequential time for preparation, and use g (k, y) in total parallel time where g (k, y) >> y.


Difficulty understanding the use of arbitrary function for the worst case running time of an algorithm In CLRS the author said
"Technically, it is an abuse to say that the running time of insertion sort is $O(n^2)$,
since for a given $n$, the actual running time varies, depending on the particular
input of size $n$. When we say “the running time is $O(n^2)$,” we mean that there is a
function $f(n)$ that is $O(n^2)$ such that for any value of $n$, no matter what particular
input of size $n$ is chosen, the running time on that input is bounded from above by
the value $f(n)$. Equivalently, we mean that the worst-case running time is $O(n^2)$.
"
What I have difficulties understanding is why did the author talked about an arbitrary function $f(n)$ instead of directly $n^2$.
I mean why didn't the author wrote
"When we say “the running time is $O(n^2)$,” we mean that for any value of $n$, no matter what particular input of size $n$ is chosen, the running time on that input is bounded from above by
the value $cn^2$ for some +ve $c$ and sufficiently large n. Equivalently, we mean that the worst-case running time is $O(n^2)$".
I have very limited understanding of this subject so please forgive me if my question is too basic.

I think that the point that the authors are trying to make is the following:

The exact running time depends on the input.

When we say that the running time of insertion sort is $O(n^2)$, what we really mean is:

The worst-case running time of insertion sort is $O(n^2)$.

Actually, we could be even more verbose, and mention that by worst-case we mean worst case with respect to the length of the array:

The worst-case running time of insertion sort, in terms of the length $n$ of the input, is some function $f(n)$ which belongs to the class $O(n^2)$.

This is equivalent to the following claim:

There exists $C$ such that insertion sort takes time at most $Cn^2$ when running on an input of length $n$.

Note that there is no need to specify a lower bound on $n$ – if the running time is bounded by $C_1n^2$ for all $n \geq N$, then it is bounded by $C_2n^2$ for all $n \geq 1$. You can take $C_2$ to be the maximum between $C_1$ and the worst-case running times on inputs of length at most $N$.


Given an array of n unsorted integers, how can you check that any 2 elements within k distance of some element don't vary by a multiple of 2? In O(n log k) time?

The input is the array of integers n, and some integer k. The output should be a boolean for whether or not the following condition holds for all elements: any two elements within k distance of this element cannot vary by a multiple of two (the maximum cannot be double the minimum).

The brute force solution would be to iterate over every element, and then iterate over all elements within k distance of it, finding the maximum and minimum, and checking to make sure the maximum is less than 2x the minimum.

However, that would take O(nk) time. Is there a way to do this in O(n log k)?

I was thinking about maintaining a min heap and a max heap (as insert and delete operations have a runtime of O(log k)), but it seems like a lot of extra work (you would have to keep a hashtable of element positions in the heap in order to remove them).

Any ideas?

Yes, it can be done in $O(n \log k)$ time, using exactly the approach you hinted at.

You're going to do a linear scan over the array, from left to right.  At each step, you check whether the max of the last $k$ elements is more than twice the min of the last $k$ elements.

To compute the max and min efficiently, you'll maintain a max-heap of the last $k$ elements, and a min-heap of the last $k$ elements.  Each time you move one element to the right, you add an element to each heap (insert $A[i]$ into the heap) and remove an element from each heap (delete $A[i-k]$ from the heap).

To remove elements from the heap, have two auxiliary arrays, $B$ and $C$.  $B[i]$ maintains a pointer to where $A[i]$ is stored in the max-heap, and $C[i]$ maintains a pointer to where $A[i]$ is stored in the min-heap.  To reduce space consumption, you can arrange that these two auxiliary arrays are of length $k$ rather than length $n$, if that is important.


When proving a set is not regular is it enough to prove a subset of it regular? E.g. when proving L = {w in {a,b}^*: the first, the middle, and the last characters of w are identical}, can i just prove ab^pab^pa is not regular? Where p is the pumping length?

I think you mixed up a few things here. Say, L is indeed regular. Then the pumping lemma guarantees us a pumping length.

If we want to show that $L$ is not regular, we can go on by assuming its regular and for every pumping length we find a word that cant be pumped.

This means, we need to search for a word (for example $ab^pab^pa$ as you have suggested) and show that no matter how you divide this word into the 3 pieces $x,y,z$ ($w=xyz$) of the pumping lemma, you can find an integer $n$ with $xy^nz\notin L$. This would contradict the pumping lemma and therefore the regularity of $L$.

As a side note, showing that a subset of $L$ is not regular doesnt imply that also $L$ is not regular (for example, $\Sigma^*$ is regular, but there are non-regular languages which are obviously subsets of it).


Could Subset Sum Problem Be Solved In linear Time Using Logarithmic Space? Is there any known lower bound on the complexity of subset sum problem? For example, could it be solved in linear time using logarithmic space?

No such bound is known; for all we know, it may be possible to solve it in linear time. In fact, for all we know, there might be an algorithm for it that uses $O(\log(n))$ space on its work tape.

We know one thing: There is not an algorithm which uses both linear time and logarithmic space. That is, there is a time-space lower bound! A Subset Sum instance of size $n$ can be reduced to a 3SAT instance of size $O(n^2)$ (perhaps there is a better reduction), and for 3SAT, we know that, if $t(t+s)<2$, then

$$3SAT \not\in TiSp\left(n^{t},n^{s}\right) $$

With $TiSp(t(n),s(n))$ the class of problems solvable in $O(t(n))$ time and $O(s(n))$ space. This is not the strictest bound, see Computational Complexity: A Modern Approach for more details.

But that still leaves open whether there is an algorithm which uses $O(n)$ time and $O(n)$ space. (Of course, the non-deterministic time hierarchy theorem tells us that for every $t(n)\in poly(n)$, there is a problem $L\in NP$ which provably requires $\Omega(t(n))$ time, the question is whether the subset sum problem is one of them.)

So yeah, that bound is not great. It's not the bound we deserve, but it is the bound we have right now.


How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount I know that CFG for $$ \{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is
$$ S\rightarrow ab/abb/aSb/aSbb $$ but I am not able to tweak  it in such a way that it is strictly in between m and 2m and not equal to any of m or 2m.
I want to draw PDA for the same.

For drawing the PDA what I did was to push non-deterministically  1 a and 2a's and popping them out for b one by one. How should I handle the edge case that it always doesn't push 1 a or not always 2 a's?

As you knew intuitively, you just missed the solution by a millimeter, which, however, may look like a mile away.

$S\rightarrow aabbb/aSb/aSbb$

The idea is simple. Since $ab$ and $abb$ should not be generated, what is the shortest or simplest word that can be generated?

Here is a sketch of a NPDA. When it reads the first $a$, it goes to state $q_1$. When it reads the second $a$, it goes to state $q_2$. Then every time if it reads one $a$, it will push one or two $a$'s nondeterministically onto the stack. Then when it reads the first $b$ it goes to state $q_4$.  When it reads the second $b$ it goes to state $q_5$. When it reads the third $b$ it goes to state $q_6$. Then every time if it reads one $b$, it pops out one $a$ from the stack, staying at state $q_6$.

I will let you flesh out the details.


linklist and memory issues I have a doubly link-list like this

typedef struct Record
{
   int i;
   Record* next;
   Record* prev;
}Record;

I have over 5 trillions of records that I need to handle, now that I need to retrieve all of them and sort them out.
If its size was small, I could borrow stl's vector or list to do the job but now that it is too huge, I have no idea how to save the object data before sorting is performed

my function prototype

void sortRec(Record**recToSort,bool bASC){}

You should also have a look at External Sorting algorithms. This is another book on the subject Algorithms and Data Structures for External Memory


"Minimum" maximum flow with extra capacities Problem:

Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, find a total extra capacity needed E so that maximum flow from source to sink is greater than or equal to F and flow in each edge that has nonzero flow.

I don't know how to solve this variation of maximum flow problem. It is obvious that if maximum flow I find without extra capacities is greater than or equal to F, then there is no need for extra capacity. If it is less than F, should I add extra capacity in each edge one by one and find max flow again till I find the closest one to F (if it is not enough, then take in pairs, triplets, etc.)? This solution seems inefficient to me.

EDIT:

Example:

Suppose source is node 0 and sink is node 5. Sink requires flow of 6 (F = 6). For the following format

(1st node, 2nd node), current capacity, extra capacity that can be added

we have following edges

0 1 3 0
0 3 3 0
1 2 3 0
1 3 2 0
2 4 4 0
2 5 2 2
3 4 2 1
4 5 3 1

Maximum flow from current capacities is 5 which is not enough for the sink (5 < F). The extra capacity from 3 to 4 and 4 to 5 is required. So total extra capacity is 2 (E = 2) and the flows are

0 1 3
0 3 3
1 2 3
2 4 1
2 5 2
3 4 3
4 5 4

The smarter Naive approach of extending a solution to the Maximum Flow problem to a similar graph with at least as much capacity is to only add flow to augmenting paths that you'd find from the Residual of the initial graph. And if no augmenting paths exist, then terminate. This is known as the Ford-Fulkerson Algorithm, and if you were to have run it on the a graph of $E$ edges initially, this would incur a runtime of $O(E\cdot f^*)$, where $f^*$ is the maximum flow in the graph.

In case you haven't heard of some of these terms, or the Algorithm, visit: http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm


Complexity Classes (P, NP) vs Language Hierarchies (REC, RE) NOTE: The statement of this question has a LOT of misconceptions.

Is there any relation between the Complexity Classes (like P or NP) and Language hierarchies (like REC or RE) ?

  Form what I understand: (easy things are the things that can be done in polynomial time span, as opposed to tough things. Tough things require exponential time span or even infinite time to finish).

P

These are the set of problems which can be easily solved. If multiple answers exist, then all those answers can be easily found.

NP

These are the set of problems, for which a tentative answer can be easily verified. Some of these problems can even be easily solved. Others are tough to solve but either way, given a tentative solution, that can be easily verified.

For those which can be easily solved, fall under the P class. Hence P <= NP. The equal sign is something scientists are still working on.

These problems can be solved easily on a non-deterministic Turing Machine. Unfortunately, such a machine does not exist. The real deterministic Turin Machines (our laptops) cant guarantee how much time it would take to solve such a problem. it might even hang.

REC

These are the set of strings (a language) which belong to one family of strings. The family is called The Grammar. Given a Grammar and a string, if we can easily tell whether the string is member of the family, then the family is REC family.

RE

These are an even broader set of strings, which belong to an even broader family. Some of the members of this family are REC, but some are not. That is, given a Grammar and a string, we may or may not easily tell whether the string is a member or not. If we are able, then the family is REC, if we are not, then it is RE family.

Membership in RE family cannot be easily verified but, given such a Grammar, all the members can be easily listed-out. Hence the name- recursively enumerable.

  Now, Question: both (P/NP) and (REC/RE) seem similar. I know they are not the same. One is problem, another is language. But is there any connection between the two?

Also, From what I understand, is there anything wrong in my understanding? I mean certainly there must be things missing. But for the part which is not-missing, is there anything wrong?

All the classes you mention are classes of languages, formally, even if P and NP are often discussed in different (more sloppy?) terms. Note that terminology revolving around decision problems is equivalent to formal languages; the decision is always whether a word is in the given language, i.e. the problem is to solve the word problem.

What you need to do is go back to the formal definitions. Summarising:

$\mathrm{RE}$ contains languages which are accepted by any TM.
$\mathrm{REC}$ contains all languages which are decided by any TM.
$\mathrm{NP}$ contains all languages which are accepted by any polynomial-time TM.
$\mathrm{P}$ contains all languages which are decided by any polynomial-time and deterministic TM.

It's already quite clear from the definitions that we have

$\qquad\displaystyle \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{REC} \subseteq \mathrm{RE}$.

So, essentially, computability and complexity theory deal with the same kind of questions: which kinds of problems can I solve with which type of machine?

In fact, the famous Complexity Zoo diagram (via the companion the wiki) displays "computability", "complexity" and "Chomsky" classes in a single inclusion hierarchy -- because they all use the same formalism.

I recommend you check out some of our reference questions on computability and complexity theory; you'll the similarities.


Do we need regular expression first or finite state automata in lexical anlysing? I'm a bit confused about the concept of finite state automata (FSA) and regular expression (RE) in lexical analysis. I have reading some books about compiler construction. At the part of tokenization, all the books I read talk  about the regular expression first to recognize the tokens. For example, the regex below is to recognize the identifier:

([a-zA -Z] | _ | $ )([a-zA -Z0 -9] | _ | $)*

Then, they jumped to explain another technique which is finite state automata (FSA). As a result, some questions have come to my mind which are:

1- What part I should learn first? RE or FSA?.

2- Programmatically, which part should be converted to other to build the lexer? RE ==> FSA or FSA to RE.
3-Since all tokens can be recognized by regular expression, then, why we need finite state automata?.

Sorry for the to many questions, but I really can't figure out how to start. many thanks in advance.

A regular expression is a language used to describe a finite state automaton. It allows you to define the fsa without drawing nodes and edges all over the place. The two go hand in hand in that regard.


Convert table look-up into function Two problems: Given a known table (boolean or int), convert it to a function that returns the same value using only simple operations (and, or, xor, sum...). For example:

bool table1[] = {0,1} converted to fun (int index) {return index;}

bool table2[] = {0,1,1,0} converted to fun (int index) {return index ^ (index>>1);}

int table3[] = {4,5,7} converted to fun(int index) {return index+4+(index>>1);}

It seems that your tables are 1-dimensional. So basically for an integer $x$ you define some value $T[x]$ and you are looking for a function $f$ such that $f(x)=T[x]$.

There is a name for the problem that tries to find a function that runs through a given set of sample points, this is known as interpolation. Your problem is special, since your sample points are given by $(x,T[x])$ and the $x$s are the indices of your table.

The most classical approach is to use a polynomial as a function (but there is also theory about other classes of functions). It is a well known theorem that if you have $n$ samples, then you can find a polynomial $f(x)=\sum_{i=0}^{n-1} a_i x^i$ that coincides with your samples. There are different ways how determine the $n$ parameters $a_i$ of the polynomial.

One way to determine the polynomial is the method of Lagrange, you define for every index $i$ of you table the coefficient
$$L_i(x):=  \prod_{j=1,j\neq i}^{n} \frac{x-j}{i-j}.$$
If you look how $L_i(x)$ behaves on the samples, then you get
$$L_i(x)=\begin{cases} 1 & x=i  \\ 0 & x= \text{table index}\not= i \end{cases}.$$

Now you can easily come up with the desired polynomial by setting
$$f(x):=\sum_{i=1}^n T[i]L_i(x).$$
You can bring $f$ in the form $\sum_{i=0}^{n-1} a_i x^i$ if you like.

Concerning you example {4,5,7}, you get $$f(x)=4 ((x - 2)/-1*(x - 3)/-2) + 5 ((x - 1)*(x - 3)/-1) +
 7 ((x - 1)/2*(x - 2))),$$
which simplifies to
$$f(x)=4-\frac{x}{2}+\frac{x^2}{2}.$$

For further reading visit the Wikipedia page on interpolation.

Here is a final remark. The table has in almost all cases the more compact representation, and it has the faster look-up time for sure.


Modeling tiling problems as SAT problems I read that tiling problems can be modeled as satisfiability problems (2-SAT?), but the author did not explain how. Is this true? What would be an example?

By a "tiling problem" I mean you have a matrix and have to fill it up according to some constraint. For example, you might have to fill the matrix with a particular shape, or the values in the matrix have to adhere to some constraint. For example, imagine a partially filled matrix and the rule is that you have to fill it with values that are one more or one less than the adjoining values, or something like that.

One example of a tiling problem that was successfully attacked by reducing it to a SAT instance was rectangular grid coloring.  In "Extremely Complex 4-Colored Rectangle-Free Grids:
Solution of Open Multiple-Valued Problems" the authors describe how they tackled 17x17, 17x18, and 18x18 grid colorings using a SAT solver plus some previous knowledge of grid coloring theory to pare down the search space.


Are the following Big Oh Notations equivalent? In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent.
$\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$

$\mathcal{O}((log(n))^{-1})$ can be rewritten as
  $\mathcal{O}(1/(log(n)))$  which is
$\mathcal{O}(1)/ \mathcal{O}(log(n))$ . This can be simplified to
$1/ \mathcal{O}(log(n))$
which is the same as the RHS. Would this be a possible solution? Any mistakes that are pointed are welcome.

This kind of thing just doesn't work. For example, one of your intermediate terms is $O(1)/O(\log n)$. However any function $f$ can be written as $g/h$ where $g=O(1)$ and $h=O(\log n)$.  If $f=O(1)$, then let $g=f$ and $h=1$. If $f=\Omega(1)$, then let $g=1$ and $h=1/f$.

For a more formal treatment, try to rewrite each of your statements that involve big-$O$ in terms of "There are constants $k$ and $n_0$ such that, for all $n\geq n_0$, $f(n)\leq k\,g(n)$." You'll probably find that it's not even clear what these formal statements should be and that, if you manage to figure that out, then some of the formal statements will be false.

The underlying point you've overlooked is that big-$O$ provides upper bounds but, if you have a quotient $a/b$ then upper-bounding that quotient requires upper-bounding $a$ and lower-bounding $b$. Big-$O$ can't express that lower bound.


Check if one condition includes another I have two conditions A and B in a form of "ast tree".
How can I check that B is more strict than A?
I.e. if B is true then A is always true.

Example

A:
x = 1 and (b = 2 or c = d)

B:
y = 5 and x = 1 and (b = 2 or c = d)

Does B include A -> true

A:
x = 1 and (b = 2 or c = d)

B:
y = 5 and x = 1 and (b = 2 or c = d)

Does B include A -> false

This seems to be a common task for a specialist in logical math.
But I have only very basic knowledge about logical arithmetics.
Any articles/studies about subject appreciated.

If your ASTs have a small number of conditions, then you can use the following naive approach.

1) Convert your ASTs to a CSOP (Canonical Sum Of Products) expression.
     From your example, lets convert each condition to a boolean variable and express $A$ and $B$ as boolean expressions in the following variables

$p: (x ==1)$
$q: (y==5)$
$r: (b == 2)$
$s: (c == d)$

Now
$ A: \space p \cdot (r + s)$
$B: p \cdot q \cdot (r + s)$
Normalising $A$ and $B$ yields
$A: p \cdot \lnot q \cdot r \cdot \lnot s +
   p \cdot \lnot q \cdot r \cdot s +
   p \cdot q \cdot r \cdot \lnot s +
   p \cdot q \cdot r \cdot s +
   p \cdot \lnot q \cdot \lnot r \cdot s +
   p \cdot q \cdot \lnot r \cdot s
$
$B: p \cdot q \cdot r \cdot \lnot s +
   p \cdot q \cdot \lnot r \cdot s +
   p \cdot q \cdot r \cdot s
$

2) Check if $ B \subseteq A$. In the above example it is true. This implies $B$ is stricter than $A$. If thought logically, all conditions in $B$ are fulfilled by $A$, but $A$ also satisfies other conditions not in $B$.
Hence, $B$ is stricter compared to $A$.

Note: Expanding boolean expressions to normal forms requires exponential space. The algorithm might need some optimisation tweaks for larger expressions.


big O of a complex function I have a complex function, which looks something like this:

$$f(x) = \sum_{k=0}^x{\frac{g(k)}{h(k)}} + l(x)$$

Now, $g(k) = O(\log k)$ and $h(k) = O(k)$, the sum iterates $k$ from $0$ to the parameter $x$ and $l(x)$ is meant to provide a decimal correction, but its form is $\dfrac{a^{b-x}}{h(k)} (a,b - const)$.

How can I assess the big O of $f(x)$?

I did some calculations and came up with $O(x^2 \log x)$, but I'm not confident it is right.

I'm assuming you meant $l(x) = a^{b-x}/h(x)$, where $a \geq 1$. This term is $o(1)$ so can be ignored. For the main term, we cannot conclude anything since we only have an upper bound on $h$; we would like a lower bound on $h$. It could be, for example, that $g(k) = \log k$ and $h(k) = e^{-k}$, a function certainly satisfying $h(k) = O(k)$, and in that case $f(x) = \Omega(e^x)$.

Assuming you meant $h(k) = \Theta(k)$, or at least $h(k) = \Omega(k)$, we can estimate the sum using an integral:
$$ \sum_{k=0}^x \frac{g(k)}{h(k)} = O\left(\sum_{k=0}^x \frac{\log k}{k}\right) = O\left(\int_0^x \frac{\log k}{k} dk\right) = O(\log^2 x),$$
using $\int \frac{\log k}{k} = \frac{1}{2} \log^2 k$. If $g(k) = \Theta(\log k)$ and $h(k) = \Theta(k)$ then $f(x) = \Theta(\log^2 x)$.


Best algorithm for splitting up departments such that the least unique ones are assigned per day I have a collection of people who need to be assigned to one of 10 dates. Each person is in a specific department. The departments have vastly varying amounts of people (from ten to thousands). Each date can accomodate a set amount of people, let's say 5000. My task is to assign each person to a date such that the amount of departments participating that day is as small as possible AND as average as possible. Basically every time you put a new department in a day it adds a lot of overhead (adding people doesn't) which means that doing a lot of departments in a single day is really bad. So for example, 1 huge department being assigned day 1 and 15 small ones being assigned day 2 is undesirable, it's better to do half of department 1 one day, and half on the other and then splitting the small ones such that its basically 7.5 one day and 8.5 on the other. But the less departments particpating in a day, the better. So if you had 3 days and 3 equal departments it would be undesirable to have 3 departments (1/3 of the employees of that department) participating each day, it would be better to have each department on a single day. The 'spots' have to be filled up, that is each day MUST have 5000 participants. Any ideas on how to approach this?

My first thought is to minimize the maximum, that is find a solution such that the highest amount of departments per day is the lowest it can be. Is this the best solution?

The first problem to solve is defining the problem.

In general, you have an optimisation problem. What you have not yet defined is the objective function, meaning what you want to optimise (precisely).

Based on what you describe, you might define the objective function as the max number of participants, but this is not great since for example a solution (2,2,5) (2 departments on day 1, 2 on day 2, 5 on day 2) is equal to a solution (1,1,5); such an objective function doesn't distinguish, e.g., unnecessarily splitting two departments over the first two days.

Another option is sum, but that does not help in the case of distinguishing (1,15) and (7.5,8.5).

Perhaps another option that seems to go in the direction you want is to minimise, for example, the sum of the squares, which prefers (1,1,5) over (2,2,5) and (7.5,8.5) to (1,15). But why raise to the power of 2 and not some other value greater than 1?

These are all application-dependent choices that you have to make.

The second problem is the difficulty. You have many options and you want to find the best option according to your objective function. Your general problem is an NP optimisation problem, so you may need to consider approximations. But again, the need to consider approximations depends on the size of your data, the values you choose, how you define the optimisation function, what is the relative cost of computation versus the cost of not finding an optimal solution, and so forth.

So after you define your objective function, you will need to think about what sort of approximation (if any) is cost effective.


Unconditional arithmetic circuit lower bounds for permanent/determinant In this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.1090&rep=rep1&type=pdf an unconditional lower bound (provided constants used are bounded by absolute value smaller than $1$) of $\Omega(n^2\log n)$ for size of arithmetic circuits computing $n\times n$ Matrix Multiplication is given.

What is the best unconditional lower bound for size of arithmetic circuits computing $n\times n$ Matrix Determinant and Permanent along similar lines?

Kalorkoti gave an $\Omega(n^3)$ lower bound on arithmetic formulas for the determinant and permanent. As far as I know, nothing is known for unrestricted circuits.


Implementation/translation of the $s^1_1$ This is the Lisp code (from wikipedia) that implements the $s^1_1$ form of the $s^m_n$ theorem

(defun s11 (f x)
   (let ((y (gensym)))
     (list 'lambda (list y) (list f x y))))

since I don't know Lisp, can someone explain me what this code does and/or translate this code into other languages

Roughly, s11 a program which takes as its first argument a representation of a 2-arguments program e.g. a string like

def foo(x,y):
   return g(x,y)

and a number n as its second argument.

The result of s11 is the representation of another program, obtained by "hard-coding" the value n for x in the source code, effectively removing the argument x. In the example above we would get the string

def newFoo(y):
   return g(n,y)

or something equivalent to that, e.g.

def newFoo(y):
   return foo(n,x)
def foo(x,y):  # original code unaffected
   return g(x,y)

The code posted by the OP does this using LISP lambdas. The part

(let ((y (gensym)))

generates a new variable name y, while

(list 'lambda (list y) (list f x y))))

returns the representation of the function

$$
\lambda y.\ f (x, y)
$$

where x is the value to "hard-code" (the one which we called n above).

The representation is a LISP s-expression / tree instead of a string, but the concept is the same. LISP is famous for being able to express code as data (roughly as an AST), and being able to run it in a simple way (homoiconicity).


how to prove that every finite language is context-free? I am trying to prove that every finite language is context-free, is there any type of way that I could do it effectively?

It's not hard to show that every finite language is regular. If you know that every regular language is also context-free, you're done.


What's the meaning of the $\top$ symbol in a Hoare triple? I'm studying program verification and came across the following triple:
$$ \{\top\} \;P \; \{y=(x+1)\} $$
What's the meaning of the $\top$ symbol on the precondition? Does it mean $P$ can take any input?

The symbol $\top$, known as top, stands for "True". There is also a symbol $\bot$, known as bottom, which stands for "False". Top is always true, and bottom is always false. In your case, having a precondition that always holds is the same as having no precondition.


NP with a parallelism model? Can we think of NP using a parallelism model instead of using a "checking relation" without loss of generality?

From what I understand from the problem statement given by Stephen Cook,

  The notation NP stands for “nondeterministic polynomial time”, since
  originally NP was defined in terms of nondeterministic machines (that
  is, machines that have more than one possible move from a given
  configuration). However, now it is customary to give an equivalent
  definition using the notion of a checking relation, which is simply a
  binary relation R ⊆ Σ ∗ × Σ ∗ 1 for some finite alphabets Σ and Σ1. We
  associate with each such relation R a language LR over Σ ∪ Σ1 ∪ {#}
  defined by LR = {w#y | R(w, y)} where the symbol # is not in Σ. We say
  that R is polynomial-time iff LR ∈ P. Now we define the class NP of
  languages by the condition that a language L over Σ is in NP iff there
  is k ∈ N and a polynomial-time checking relation R such that for all w
  ∈ Σ ∗ ,w ∈ L ⇐⇒ ∃y(|y| ≤ |w| k and R(w, y)), where |w| and |y| denote
  the lengths of w and y, respectively.

it appears that the definition of NP given here can be derived from the definition of non-deterministic Turing machines. From this lecture document from the University of Illinois:

  Formally, a nondeterministic Turing machine has all the components of
  a standard deterministic Turing machine—a finite tape alphabet Γ that
  contains the input alphabet Σ and a blank symbol ; a finite set Q of
  internal states with special start, accept, and reject states; and a
  transition function δ. However, the transition function now has the
  signature δ: Q × Γ → 2 Q×Γ×{−1,+1} . That is, for each state p and
  tape symbol a, the output δ(p, a) of the transition function is a set
  of triples of the form (q, b,∆) ∈ Q × Γ × {−1,+1}. Whenever the
  machine finds itself in state p reading symbol a, the machine chooses
  an arbitrary triple (q, b,∆) ∈ δ(p, a), and then changes its state to
  q, writes b to the tape, and moves the head by ∆. If the set δ(p, a)
  is empty, the machine moves to the reject state and halts. The set of
  all possible transition sequences of a nondeterministic Turing machine
  N on a given input string w define a rooted tree, called a computation
  tree. The initial configuration (start, w, 0) is the root of the
  computation tree, and the children of any configuration (q, x, i) are
  the configurations that can be reached from (q, x, i) in one
  transition. In particular, any configuration whose state is accept or
  reject is a leaf. For deterministic Turing machines, this computation
  tree is just a single path, since there is at most one valid
  transition from every configuration.

This mentions the notion of a computation tree:

Thus, suppose I were to have a machine that was able to compute all of the non-deterministic branches in parallel such that the bounded running time is $O(poly(n))$. Is this an equivalent of a Turing machine such that a language that is accepted by this machine is within $NP$?

In a sense, we can also see that if a deterministic machine were to choose the "right" branch by chance that it's somewhat equivalent to the notion of an oracle. This seems like it's similar to the "checking relation" in the sense that we need only compute one branch's result in order to determine acceptance of the answer or rejection. Is this intuition right?

And, in addition, can the deterministic machine can simulate the computation of the non-deterministic machine in $O(2^n)$ time?

Edit: If we make the addition that one of the paths are guaranteed to accept, then is the machine now equivalent to NP?

Your description of NP is still missing the accept criterion. For example you might decide to accept the input exactly in case all computation paths accept. This would give you the class coNP instead of NP. Or you might decide to accept the input exactly in case half of the computation paths accept. But for NP, the accept criterion is that there exists at least one computation path which accepts. Other than that, your parallelism model of NP is perfectly fine. And yes, the deterministic machine can simulate the computation of the non-deterministic machine in $O(2^n)$ time!


What are predicates of a sentence? I am reading Handbook of Satisfiability in which they say:

  An algebraic structure, or simply structure, consists of a non-empty set of
  objects existing in the world $w$, called the domain and denoted below by $D$, and
  a function, called an interpretation and denoted below by $R$, that assigns to each
  constant an entity in $D$, to each predicate a relation among entities in $D$, and to
  each functor a function among entities in $D$.

  A sentence $p$ is said to be true in $w$
  if the entities chosen as the interpretations of the sentence’s terms and functors
  stand to the relations chosen as the interpretation of the sentence’s predicates.

In this context, could you help me with some example of predicates of a sentence? And what does "stand to" mean here?

I am not a native English speaker, maybe this is why I can not understand this claim.

Roughly, a sentence is just logical syntax: it's simply a string in the language of logic. E.g. a sentence $\phi$ could be
$$
    {\sf eats}({\sf cat}, {\sf head}({\sf tuna}))
$$
Above $\sf eats$ is a predicate symbol, $\sf head$ is a function symbol (which your book calls "functor"), while $\sf cat, tuna$ are constant symbols.

A structure defines how to interpret the symbols. For instance, we can choose the domain $D$ to be the set of real numbers $\mathbb{R}$. Then, we interpret the symbols as follows:
$$
\mbox{World $w$: }\qquad\qquad
\begin{array}{l}
  [\![ {\sf cat} ]\!]^c = 5 \\
  [\![ {\sf tuna} ]\!]^c = 4 \\
  [\![ {\sf squirrel} ]\!]^c = 2 \\
  \ldots \\
  [\![ {\sf head} ]\!]^f = g \mbox{ where } g(x) = \pi \cdot x \\
  \ldots \\
  [\![ {\sf eats} ]\!]^p = \{ \langle x , y \rangle \ |\ x < y \}
\end{array}
$$
(A structure can define more symbols than those used in the formula, hence
the $\sf squirrel$ above.)

Constant symbols are interpreted as elements of $D$ by the interpretation $[\![-]\!]^c$.
Function symbols are interpreted as functions $D\rightarrow D$ by the interpretation $[\![-]\!]^f$.
Predicate symbols are interpreted as subsets of $D^k$ ($k$-ary relations, where $k$ is the number of arguments of the predicate) by the interpretation $[\![-]\!]^p$.

The sentence $\phi$ is satisfied by the structure $w$. This is because, if we interpret everything, we have
$$
  [\![ {\sf eats} ]\!]^p ([\![ {\sf cat} ]\!]^c, [\![ {\sf head} ]\!]^f([\![ {\sf tuna} ]\!]^c))
$$
which is
$$
  < (5, g(4))
$$
i.e.
$$
  5 < \pi \cdot 4
$$
which is true. The sentence $\phi$ is said to be satisfiable: there is some structure which makes it true.


Evaluation metric for an ordering algorithm There is a sentence with N words.

The words are randomly shuffled.

I have a heuristic algorithm that tries to restore the original order.

I want to evaluate my algorithm on a dataset of several hundred long sentences from the internet.

The main goal of the algorithm is that humans looking at the restored sentence will be able to easily know what the original sentence was. So I can evaluate my algorithm by asking humans to grade the quality of the restored order. However, this is very expensive.

Another option is to count the number of words that are in their correct position in each sentence, and divide by the total number of words in all sentences. However, this is not a good measurement of the quality, because, for example, if the only mistake of my algorithm is that it put the last word first, the resulting sentence will get a score of 0, although it is quite similar to the gold standard, and a human will easily notice this.

A third option is to find the minimum number of word moves that need to be done on the algorithm output in order to achieve the gold standard. However, this seems like a non-trivial task in itself.

Can you suggest a measurement that will be both meaningful and easy to implement?

One standard measure is the Kendall tau distance, which is the number of "inversions", i.e. positions $i < j$ such that $\pi(i) > \pi(j)$. It is also the number of transpositions $(k \; k+1)$ you need to apply to sort $\pi$, or vice versa, the number of such transpositions needed to generate $\pi$. (So it's the distance metric in the Cayley graph of $S_n$ with respect to the transpositions $(k \; k+1)$, which form a generating set.)


Calculating a polynomial's coefficients from its roots Let $P$ be a monic polynomial polynomial given by its roots:
$$P(X) = (X-x_1)\times...\times(X-x_n)$$

What is the minimum asymptotic complexity to compute its expansion of the form:
$$a_nX^n+...+a_0$$

What I have found so far are Vieta's formulas which give an expression of each $a_k$ as a sum over $1\leq i_1 < ... < i_{n-k} \leq n$. This would suggest the complexity of computing the $k$th coefficient is something like ${n-1 \choose n-k-1}={n-1 \choose k}=O(n^k)$, thus making the total complexity bonkers (I guess something like $O(n^n)$).

Yet my teacher's presentation suggests it is a $O(n^2)$, which doesn't match my calculation at all.

For every integer $i$, $0\le i\le n$, let
$$P_i(X) = (X-x_1)(X-x_2)\cdots(X-x_i)=a_{i,i}X^i+a_{i,i-1}X^{i-1}+\cdots+...+a_{i,0}$$
for some $a_{i,k}$, $0\le k\le i$. In particular, $a_{i,i}=1$. Expanding $P$ on both sides of the following equation and comparing the coefficients,
$$P_{i+1}(X) = P_i(X)(X-x_{i+1})$$
we see that for $1\le k\le i\lt n$,
$$a_{i+1,k}=-a_{i,k}x_{i+1}+a_{i,k-1}$$
and
$$a_{i+1,0} = -a_{i,0}x_{i+1}$$
So for fixed $i$, we can compute all coefficients of $P_{i+1}(X)$ from the coefficients of $P_i(X)$ with $O(i)$ steps. Now you should be able to see that your professor's suggestion on the minimum asymptotic complexity makes a lot of sense.


General structure of solutions to 3-SAT circuits Certain special forms of the SAT problem have solution sets of a special form. For example, given any three solutions to a 2-SAT circuit, their bitwise median is also a solution. Likewise, given any three solutions to an XOR-SAT circuit, their bitwise XOR is also a solution. Lastly, given any two solutions to a HORN-SAT circuit, their bitwise AND is also a solution.

Does there exist a similar situation for 3-SAT, where given some subset of solutions, one can somehow generate additional solutions?

If not, does there exist a related SAT problem that 3-SAT can be reduced to, and hence which is also NP-complete, which have solutions of the form specified? For instance 1-in-3 SAT, or exactly-3-SAT, or NAE-3-SAT, or etc.

The theory you are after is universal algebra. See the excellent expository article of Hubie Chen, A rendezvous of logic, complexity, and algebra, which contains a streamlined proof of Schaefer’s dichotomy theorem, which was recently extended to arbitrary alphabets.

3SAT has no polymorphisms. NAE-3SAT has only negation as a polymorphism. All other classes of polymorphisms correspond to CSPs solvable in polynomial time. See Allender et al., The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem.


Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$ Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed by the grammar $S \rightarrow aSa\ |\ aa$.

It appears to only parse words from the language $\{a^{2^n}\ |\ n \ge 1 \}$.

I generated such a parser using this ABNF Parser Generator with the production rule S = "a" S "a" / "aa" and the parser does not recognize the word aaaaaa, for example.

I would expect it to use the production $S \rightarrow aSa$ until the concatenation of the parse tree's terminal nodes from the left starts with 7 a's, and then go up the parse tree choosing the production $S \rightarrow aa$ instead until the tree looks like this:

   S
 / | \
a  S  a
 / | \
a  S  a
  / \
 a   a

This is not much of an answer, but the parse trees do not fit the
normal comments.

Your grammar $S \rightarrow aSa\ |\ aa$ should parse the string
$aaaaaa$.

But the parse tree has the following form:

      S
     /|\
    / S \
   / /|\ \
  / / S \ \
 / / / \ \ \
a a a   a a a

or if you prefer this presentation, with the terminals on different
lines

     S
   / | \
  a  S  a
   / | \
  a  S  a
    / \
   a   a

I checked that the ABNF parser generator does not seem to work, but I
do not know how to trace what it does.

It indeed seems to recongnize the set  $\{a^{2^n}\ |\ n \ge 1 \}$ wich
is not what the grammar defines.

It is a bit surprising to have such an elaborate site around a buggy parser,
which furthermore uses a totally uninteresting parsing technique.

After a further look at it:

I think I found one source of the problem. The square brackets mean
optional.

So your grammar should be written either
S = "a" S "a" / "aa"
or S = "a" [S] "a". Then it seems to work correctly.

But the system is apparently lost when having twice the same rule in
different forms. I am not sure why.

I did not find a page explaining these syntactic issues for specifying
the grammar.

I still consider that buggy.


If set $C$ is recursively enumerable and $B$ is Recursive, and if $B-C$ is recursively enumerable then is $C$ recursive or not? So this is how i solve it but someone told me its wrong:

$B-C = B\cap \overline C $ and since $B\cap \overline C $ is r.e and B is recursive recursive sets are closed under intersection then $\overline C $ is not Recursive(because if both of them were recursive then the intersection would be recursive), also since r.e sets are closed under intersection then $\overline C $ must be r.e

and since $\overline C $ and $C$ are r.e then C is recursive

so am i wrong? is C recursive or not and why?

The argument is wrong.

Your argument is: $B\cap \bar C$ is r.e., $B$ is recursive, so $\bar C$ has to be non recursive, otherwise $B \cap \bar C$ would be recursive -- contradiction.

However, there is no contradiction: $B\cap \bar C$ can be both r.e. and recursive. This is equivalent to $B\cap \bar C$ being recursive. There is no hypothesis contradicting that.

Indeed, take $C$ to be the halting problem (r.e., and not recursive). Take $B=\emptyset$ which is recursive. Then $B\cap\bar C = \emptyset$ which is (recursive and) r.e. . So all the hypotheses are satisfied, but $C$ is not recursive.


How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$ In the book CLRS the authors say that every quadratic, asymptotically nonnegative function $f(n) = an^2 + bn + c$ is an element of $\Theta(n^2)$. Using the following definition

  \begin{align*}
\Theta(n^2) = \{h(n) \,|\, \exists c_1 > 0, c_2 > 0, n_0 > 0 \,\forall n \geq n_0: 0 \leq c_1n^2 \leq h(n) \leq c_2n^2\}
\end{align*}

the authors write that $n_0 = 2*\max(|b|/a, \sqrt{|c|/a})$.

I have difficulties proving that the value of $n_0$ is indeed that value.

We know that $a \ge 0$ because otherwise $f$ would not be asymptotically nonnegative. Calculating the roots of $f$ gives us:

\begin{align*}
n_{1/2} &= \frac{-b \, \pm \, \sqrt{b^2 - 4ac} }{2a} \\
        &\leq \frac{|b| + \sqrt{b^2 - 4ac} }{a}
\end{align*}

The case $c \ge 0$ gives us:

\begin{align*}
\frac{|b| + \sqrt{b^2 - 4ac} }{2a} \leq \frac{|b| + \sqrt{b^2}  }{a} = 2\frac{|b|}{a}
\end{align*}

which is two times the first argument of the $\max$ function.

But what about the case $c < 0$? How can we find an upper bound for that? Where does the value $\sqrt{|c|/a}$ actually come from?

So I actually found the answers I was looking for. The case $c \ge 0$ is already handled in the question above. For the case $c < 0$ we have:

\begin{align}
n_{1/2}
&=   \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\
&\le \frac{|b| + \sqrt{b^2 - 4ac}}{a}   \\
&\le \frac{|b| + \sqrt{b^2} + \sqrt{-4ac}}{a} \\
&=   \frac{2|b| + \sqrt{4a|c|}}{a}  \\
&=   \frac{2|b| + 2\sqrt{\frac{a^2|c|}{a}}}{a} \\
&=   2\frac{|b|}{a} +  2\sqrt{\frac{|c|}{a}} \\
&\le 2\max(\{|b|/a, \sqrt{|c|/a}\}) \\
&= n_0
\end{align}

This value for $n_0$ includes the case $c \ge 0$. If $f$ doesn't have any roots, we can instead choose $n_0 = 1$.

For the constants $c_1, c_2$ the authors gave us the values $c_1 = a/4$ and $c_2 = 7a/4$. To check that these are correct we do the following:

Since $n \ge 2|b|/a$ and $n \ge 2\sqrt{|c|/a}$, we know that:
\begin{alignat}{3}
&& \frac{1}{2} &\ge  &\frac{|b|}{an} \quad&\text{and}\quad &\frac{1}{4} \ge  &\frac{|c|}{an^2} \\
&&-\frac{1}{2} &\le -&\frac{|b|}{an} \quad&\text{and}\quad -&\frac{1}{4} \le -&\frac{|c|}{an^2}
\end{alignat}

This gives us

\begin{alignat}{2}
&\frac{1}{4} =   1 - \frac{1}{2} - \frac{1}{4} \le 1 - \frac{|b|}{an} - \frac{|c|}{an^2} \le 1 + \frac{b}{an} + \frac{c}{an^2} \\
\text{and therefore}\quad
&\frac{a}{4}n^2 \le an^2 + bn + c
\end{alignat}

and

\begin{alignat}{2}
&1 + \frac{b}{an} + \frac{c}{an^2} \le
 1 + \frac{|b|}{an} + \frac{|c|}{an^2} \le
 1 + \frac{1}{2} + \frac{1}{4} =
 \frac{7}{4} \\
\text{and therefore}\quad
&an^2 + bn + c \le \frac{7a}{4}n^2
\end{alignat}

which shows that the values $c_1 = a/4$ and $c_2 = 7a/4$ are indeed correct.


Implicit complexity and interpretation of total languages In implicit complexity theory we construct languages that characterize what can be computed in various complexity classes. One major result is Bellantoni and Cook where they show that $FP$ can be characterized by such a language (called system $B$).

I have the following beliefs about system $B$

System B can encode all functions which can be computed in polynomial time
All terms in System $B$ normalize in polynomial time
Because all System $B$ terms normalize (in any amount of time) System $B$ is total
Because all System $B$ terms normalize in polynomial time System $B$ can interpret System $B$

I have the following beliefs a computability as well

If a language can interpret itself then it is not total
System $B$ can interpret it self so System $B$ is not total

So I seem to believe contradictory things now; namely that System $B$ is total and that System $B$ is not total. Writing out like this makes me realize that the error is almost certainly in the last line of my beliefs about System $B$. So it must be the case that System $B$ can't interpret itself but I don't actually understand why this is the case. Is there a program input pair such that interpreting it takes greater than polynomial time? Further still System $B$ is just one such system among all characterizations of complexity classes on which I could apply this faulty reasoning so the answer should not be specific to System $B$ but to all such implicit characterizations of complexity classes.

As concluded via non-direct means in discussion interpreting a polytime program cannot be done in polynomial time in general. The following example shows this directly.

The trick is that for the interpreter to run in polynomial time there must be an polynomial that bounds the running time for every input. This pretty obviously isn't going to hold for System-$B$ because a small constant increase in program size can increase the order of the polynomial that bounds it by a constant amount. The trick you can fall into (and I indeed fell into) is to think that because for each program the running time is bounded a polynomial that the interpreter will run in polynomial time which is pretty embarrassingly obviously false when you write it out like this. It's running time on certain inputs will be bounded by some polynomial but that's the case for any program that always terminates.

So say there is a program, $I$ in System-$B$ that interprets System-$B$ and has running time in $O(n^k)$. Say I had another program, $P$, that ran in $O(n^K)$ with $K > k$. We could speed up P to $O(n^k)$ by simply running it though the interpreter first. So suddenly you have a huge speed up on $P$ that you shouldn't be able to get. In general $I$ could speed up any program slower than it.

I don't have a proof there is no $k$ such that every polytime function can be computed in $O(n^k)$ but it seems fairly obviously the case.


Changing Rabin-Karp without modulo to Rabin-Karp with modulo I am trying to solve a string matching problem using Rabin-karp algorithm.

I made use of Horner's method for calculating hash function, but I forgot to use modulo operator. It's like this now.

(this is for starting pattern length of the big string)

  1     for(i=0;i<l1;i++)
  2     {
  3         unsigned long long int k2 = *(s1+i);
  4         p1 += k2 * k1;
  5         k1 = (k1 * 31);
  6     }

where s1 is a string containing characters,and its like

  s1[0]*(k1^0) + s1[1]*(k1^1) and so on.

and I did the same for the pattern we need to find:

  0     unsigned long long int j;
  1     for(j=0;j<l1;j++)
  2     {
  3         unsigned long long int k3 = *(str+j);
  4         p2 += k3 * k4;
  5         k4 = (k4 *31);
  6     }

Now I am going through strings of length = pattern length in the big string.
     Code for that is:

  0  long long int ll1 = strlen(s1),ll2=strlen(str);
  1     for(j=1;j<=ll2;j++)
  2     {
  3         printf("p1 and p2 are %d nd %d\n",p1,p2);
  4         if ( p2 == p1)
  5         {
  6             r1 = 1;
  7             break;
  8         }
  9         long int w1 = *(str+j-1);
 10         p2 -= w1;
 11         p2 = p2/31;
 12         long int lp = *(str+j+l1-1);
 13         p2 += ((lp *vp));
 14  }
 15     if ( r1 == 0)
 16     {
 17         printf("n\n");
 18     }
 19     else
 20      {
 21           printf("y\n");
 22      }
 23    }

where str is the big string, s1 is pattern string.

I tested for multiple inputs and I am getting correct answers for all of them but its taking a lot of time. I then realized it's because of high calculations needed when the pattern string is too long and if we use a modulo operator we can minimize those calculations.

  My question is how to incorporate modulo operator in this code while searching for patterns?

My entire  code:
http://ideone.com/81hOiU

Don't wait to do the modular reduction at the end.  Every time you do an addition or multiplication, immediately reduce modulo the modulus.  This keeps all intermediate results small.


How a NTM reject an input / How a TM simulates a particular NTM I understood that a NTM can say only yes but it doesn't know if the input is a NO instance with a single execution. Furthermore, the NTM can diverges and, at the same time, can decide a language (source: Papadimitrou - Computational Complexity, proposition 7.1). While a TM must converges in a "yes" or "no" answer to decide the same language.
Now, we know that for a NTM that decides a language L we can create a TM that decides L
(theorem 2.6). But suppose that the NTM diverges for some computation. How can the TM treat this case?

[EDIT] Definition (source Papadimitrou, pg 45):
A non-deterministc Turing Machine decides a language L if for any input x, the following is true: x belongs to L iff there is an acceptance path.

This definition admits machines that, instead of rejecting an input, diverge and at the same time decide a language.

Theorem 2.6 (pg 47):
Suppose that language L is decided by a nondeterministic
Turing machine N. Then it is decided by a deterministic Turing machine M.

Proposition 7.1 (pg 141):
Suppose that a (deterministic or nondeterministic) Turing
machine M decides a language L within time (or space) f(n), where f is a
proper function. Then there is a precise Tring machine M', which decides the
same language in time (or space, respectively). O(f(n)).

This last proposition confirms that there is a Turing machine that decides a language and that diverges for some path.

If we're only interested in computability, and not in the resources used by the computation (i.e., complexity), then we can simulate an NTM as follows. First, simulate every possible sequence of nondeterministic choices for one step. Then, start again and do them all for two steps. Then, start again and do them all for three steps, and so on.

There are three possible results of this simulation.

If any of the simulated computations accepts (so, in particular, it terminates), then we accept. In this case, it doesn't matter if some other computations would diverge.
If no computation accepts but, after some number of steps, all computations have rejected, we reject.
If no computation accepts and at least one computation diverges, then the simulation will also diverge.

This is a faithful simulation of the nondeterministic machine. If some computation path accepts, we accept, and this is the definition of acceptance for nondeterministic machines. If every computation path halts and rejects, we reject, as we should. Otherwise, we diverge, as does the nondeterministic machine.

However, the case you're looking at does include resource bounds. Papadimitriou is essentially comparing two different notions of the resources used by an NTM and showing that they're both the same. I'll talk about time for concreteness, but the same arguments apply to space. One way of defining $\mathrm{NTIME}(f(n))$ would be to say that every possible computation path must run within $f(n)$ steps, and the other would be to say that only the accepting paths need to. However, because we're only interested in constructible functions $f$, we can use the following idea to make the two notions identical. First, the machine deterministically computes $f(n)$ and then it does the nondeterministic computation, counting off the steps. If the step counter reaches $f(n)$, and the machine hasn't accepted, we must be either on a rejecting path or a diverging one. In either case, the path won't accept, so we can reject. Therefore, any language that's accepted by an NTM where every accepting path uses at most $f(n)$ steps is also decided by an NTM where every path uses at most $f(n)$ steps and no path diverges.

Technically, I've only shown that we can do it in something like $3f(n)$ steps, but the linear speed-up theorem says we can get rid of the constant $3$.


Showing Cycle is NL-complete? Consider the following decision problem :

  Cycle:
   Given a directed graph G, does G contains a directed cycle?

It is very clear why Cycle belongs to NL.
My question is - how to show Cycle is also NL-hard?
it seems almost obvious to show logarithmic reduction from stCON. I thought about the following reduction:

  Given a tuple (G, s, t), return G with a new edge (t,s).

Let us reduce direct connectivity to CYCLE. We are given a directed graph $G$ and two vertices $s,t$. Suppose that $G$ contains $n$ vertices. We create $n$ copies of the vertices of $G$. For each edge $x \to y$ in $G$, we add an edge from the $i$th copy of $x$ to the $(i+1)$th copy of $y$. We also add an edge from the $n$th copy of $t$ to the first copy of $s$. The new graph contains a cycle iff $t$ is reachable from $s$ in $G$.

We can construct the new graph from the original graph in logspace. Hence this is a logspace reduction, which shows that CYCLE is NL-hard.


Checking whether a number is a square or higher power modulo n Is there an algorithm to check whether an integer $x$ is a square modulo $n$, where $n$ is an integer whose factorization we do not know?  Is the Jacobi symbol helpful?

What about higher powers, e.g., testing whether $x$ is a $k$th power modulo $n$?

Recognizing squares

No.  As far as we know, there is no efficient algorithm to tell whether $x$ is a square modulo $n$, if the factorization of $n$ is not known.

This is the  quadratic residuosity problem; see Wikipedia for an overview.  The conjecture is that the quadratic residuosity problem is as hard as factoring (i.e., the best algorithm is to first factor $n$).  In fact, some cryptosystems have been built whose security rests on this assumption.

The best we can do is to use the Jacobi symbol.  If the Jacobi symbol $\left(\frac{x}{n}\right)$ is $-1$, then $x$ is certainly not a square modulo $n$.  However, if $\left(\frac{x}{n}\right)=+1$, then $x$ might or might not be a square.  In particular, if $n$ is the product of $k$ large, distinct primes, then about $1/2^k$ of all numbers modulo $n$ are squares; about $1/2$ have Jacobi symbol $+1$; so about $1/2^{k-1}$ of all numbers with Jacobi symbol $+1$ are squares, and the remaining are non-squares.  Thus, the Jacobi symbol is not enough to determine whether $x$ is a square modulo $n$.

When $n$ has known factorization

If the factorization of $n$ is known, then you can easily determine whether $x$ is a square modulo $n$ or not by using the Chinese remainder theorem.  Similarly for higher powers; again, use the Chinese remainder theorem; then check whether $x^{(p^e-p^{e-1})/k} \equiv 1 \pmod{p^e}$, for each prime $p^e$ dividing $n$.

(You might also like the following post, which discusses not only how to detect whether it is a $k$th power but whether you can compute the $k$th root, when working modulo a prime $p$: https://crypto.stackexchange.com/q/6518/351.  If the factorization of $n$ is known, this will determine when you can compute $k$th roots modulo $n$.)

So, in the rest of this answer, I'm assuming the factorization of $n$ is unknown, and $n$ is hard to factor.

Recognizing higher powers

What if we want to test whether $x$ is a $k$th power modulo $n$?  Here things bifurcate, according to whether $k$ is relatively prime to $\varphi(n)$ or not.

If $k$ is relatively prime to $\varphi(n)$, then every number $x$ that is relatively prime to $n$ is a $k$th power modulo $n$.  This follows from the fact that $(x^j)^k \equiv = x \pmod n$, where $j \equiv k^{-1} \pmod n$.  (The case where $x$ is not relatively prime to $n$ is easy to handle: you compute $d=\gcd(x,n)$ and split the problem into one of determining whether $x$ is a $k$th power modulo $d$ and whether $x$ is a $k$th power modulo $n/d$.)

If $k$ divides $\varphi(n)$, then we are in a situation analogous to that of detecting squares.  This is only case where I'm not 100% certain about the answer, and I don't know whether it has been studied or not.  (I would conjecture that detecting $k$th powers modulo $n$ is probably also hard if $n$ is hard to factor, but I have no proof.)

If $k$ is not relatively prime to $\varphi(n)$ but does not divide $\varphi(n)$, let $k'= \gcd(k,\varphi(n))$.  Then the question of whether $x$ is a $k$th power reduces to the question of whether $x$ is a $k'$th power, which is discussed above.


Does this algorithm for permuting rows and columns of a matrix converge? Given a binary matrix, define the magnitude of a row by reading off the numbers in it left to right and similarly for columns, reading the numbers going down. For instance, the row magnitude of the 1-st row of this matrix is 1001101, and for the 2-nd column it is 11.
1 0 0 1 1 0 1
0 0 0 1 1 0 1
0 1 1 0 0 1 0
0 1 1 0 0 1 0
I would like to sort a matrix by doing the following:

reorder rows so that rows are ordered in descending order according to their row magnitude

reorder columns so that columns are ordered in descending order according to their column magnitude

repeat 1 and 2 until rows and columns are in a correct order

For the matrix above this would go as follows:
sort by rows (step 1)
1 0 0 1 1 0 1
0 1 1 0 0 1 0
0 1 1 0 0 1 0
0 0 0 1 1 0 1
sort by columns (step 2)
1 1 1 1 0 0 0
0 0 0 0 1 1 1
0 0 0 0 1 1 1
1 1 1 0 0 0 0
sort by rows (step 1)
1 1 1 1 0 0 0
1 1 1 0 0 0 0
0 0 0 0 1 1 1
0 0 0 0 1 1 1
both columns and rows are in order, terminate procedure.
For the majority of matrices, performing steps 1 and 2 once won't be sufficient, since reordering columns will ruin the ordering of the rows. However, strangely enough it seems like 3 reorderings are sufficient to order matrices I've tried it on.
Despite not being able to find a counterexample, I struggle to see why this would be the case, and even more generally, what guarantees the algorithm won't get stuck in a cycle. Is there an existing name or more formal way to describe this algorithm and are there any proofs on its convergence?

For an $n \times m$ matrix $M$, define the potential function
$$
\Phi(M) = \sum_{i=1}^n \sum_{j=1}^m 2^{n-1-i} 2^{m-1-j} M(i,j).
$$
If we write it as
$$
\Phi(M) = \sum_{i=1}^n 2^{n-1-i} \sum_{j=1}^m 2^{m-1-j} M(i,j)
$$
then it immediately follows that reordering rows either fixes $M$, or strictly increases $\Phi$. Similarly, reordering columns either fixes $M$ or strictly increases $\Phi$. Since there are only finitely many $n \times m$ matrices, it follows that your algorithm eventually converges.
It is definitely not the case that the process terminates after three steps. For example, here is a matrix which requires five steps:
$$
\begin{pmatrix}
0&0&1&0 \\
0&1&0&0 \\
1&0&0&1 \\
0&0&1&1
\end{pmatrix}
$$
This is a matrix in which the $(i,j)$'th entry depends only on $i+j$. Specifically, $M(i,j) = 1$ iff $i+j \in \{4,7,8\}$.
More generally, the $n \times n$ matrix $M$ in which $M(i,j)=1$ iff $i+j \in \{4,2n-1,2n\}$ requires $2n-3$ rounds, which is optimal for small values of $n$ (over all $n \times n$ matrices). Moreover, this is the unique choice over matrices of this form.
(To complete the picture, for $n = 3$ the unique optimal choice is $i + j \in \{4,6\}$ rather than $i+j \in \{4,5,6\}$, and for $n = 2$ the only choices are $i+j \in \{4\}$ and $i+j \in \{3,4\}$, which both correspond to two rounds.)


Set that keeps unique categories of objects I would like to know if this type of special set operator exists, and if yes what is it called and if it has any other special properties.

Lets say I have this set $S$ of items. Like all sets, if the same item is added twice in the set, the set will not add it again. However, when adding an item, using this special operator, it also checks if it is 'better' than another item already in the set, and if yes it replaces it with the new item rather than letting both.

For a more concrete example:

$S_1 = \{apple, orange, pear\}$

$S_2 = \{betterApple, orange, banana\}$

$S = S_1 \cup_\succ S_2 = \{betterApple, orange, pear, banana\} $

So in this case $\cup_\succ$ checked some relationship, lets say $\succ$ where $betterApple \succ apple$, and if such a relationship existed it dropped $apple$ rather than allowing both in the set, keeping the stronger one in the set.

There is no official operation that accomplishes what you want, but you can always define an operation $\cup_{\succ}$ which does so. Just define the operation in words.

If for some reason you want a "physical" implementation, then here is one way. Each set is a collection of pairs, i.e.
$$
\begin{align*}
S_1 &= \{ (apple,apple), (orange,orange), (pear,pear) \}, \\
S_2 &= \{ (apple,betterApple), (orange,orange), (banana,banana) \}.
\end{align*}
$$
Furthermore, there is some partial order $\prec$ such that $(x,y),(z,w)$ are comparable iff $x = z$. When you take the union $S_1 \cup S_2$, you get
$$
S_1 \cup S_2 = \{ (apple,apple), (apple,betterApple), (orange,orange), (pear,pear), (banana,banana) \}.
$$
Then you can define a function
$$
\phi(S) = \{ x \in S : \text{ no $y \in S$ satisfies $y \succ x$ } \}.
$$
What you want is $\phi(S_1 \cup S_2)$.


reduction from the problem "accepts-empty string" to "language of empty string" 9.9. Construct a reduction from Accepts-$\lambda$ to the problem Accepts-$\{\lambda\}$: Given a TM $T$ , is $L(T) = \{\lambda\}$?

The question is from Martin's Introduction to Languages and Theory of Computation.

I know how reductions work though I am unsure of several things. It's easy to see that if the inner machine (computing "accepts-$\{\lambda\}$") accepts then the outer must also accept, but it is not clear that the other goes as well. How do I ensure this?

Call $L_1=\{\langle M \rangle\mid M\text{ accepts }\lambda\}$ and $L_2=\{\langle M \rangle\mid M\text{ accepts only }\lambda\}$, where $\langle M\rangle$ denotes the description of the TM $M$. We wish to establish a mapping reduction $L_1 \le_\text{M} L_2$.

To do this, we want a mapping, $f$, from TM descriptions to TM descriptions such that
$$
\langle M\rangle\in L_1 \Longleftrightarrow f(\langle M\rangle)\in L_2
$$
For a TM description $\langle M\rangle$, we'll define $f(\langle M\rangle)=\langle N\rangle$ where

N(x) =
   if x = lambda
      run M on input lambda
      if M accepts
         accept

Now what happens with this mapping?

If $M(\lambda)$ accepts (so $\langle m\rangle\in L_1)$, $N$ will accept $\lambda$ and no other string, so $\langle N\rangle\in L_2$.
If $M(\lambda)$ doesn't accept (so $\langle M\rangle\notin L_1)$, $N$ will accept no input string, so $L(N)=\varnothing$ and thus $\langle N\rangle\notin L_2$.

That's exactly what we need to establish the reduction $L_1 \le_\text{M} L_2$.


coNP and limitation of NDTM I am trying to understand if someone can apply an NTM to recognize a $coNP$ language.

From the definition we know that:

$NP$ - set of languages that can be recognized by NTM in polynomial time.

$coNP$ - set of all languages that are complement to $NP$ language.

as with $P$ vs. $NP$ question, we have $NP$ versus $coNP$ question.

Unfortunately, is not defined explicitly if can one recognize $coNP$ language with NTM.

However, if we take a look at few examples from the set of $coNP$ languages, few questions emerge.

$TAUTOLOGY$ = {$\varphi$: $\varphi$ is satisfied by every assignment}

$UNSAT$ = {$\varphi$: $\varphi$ is unsatisfiable}

These languages are known to be $coNP$ language and intuitively it seems like one can construct NTM to recognize these languages. On the other hand, if one can construct NTM to recognize them why them not in $NP$ class (by definition)? Maybe not all languages of $coNP$ can be solved by NTM, just few of them which are in  $NP\cap coNP$. And if every language from $coNP$ class cannot be solved by NTM, does it mean that limitation of NTM is located in $coNP$. Does NTM have limitation at all?

I am a little bit confused, I would appreciate anyone that is willing to shine the light on this topic.

These complexity classes are not just defined by a machine model but also by the criteria about when a machine accepts a strings. So although $\mathsf{NP}$ and $\mathsf{coNP}$ can be defined using essentially the same underlining machine structure their accepting criteria are different. That is the main point you are missing.

In my experience, generally it is intuitively more clear for people to think about $\mathsf{NP}$ using its verifier-certificate definition and forget about the non-deterministic TM (which can be confusing).

We say a language $L$ is in $\mathsf{NP}$ if there is a polytime DTM with two inputs $V$ (think of $V$ as a certificate verifier) s.t. for all $x$,
$ x \in L$ iff there exists a polynomial size certificate $y$ s.t. $V$ accepts $(x,y)$.

In more intuitive terms, $\mathsf{NP}$ is the set of problems that given an instance and a polysize solution/certificate/proof for that instance, we can efficiently verify the correctness of the given solution.
E.g. given a graph and a list of vertices in it, it is possible in polynomial time to check if the list is a Hamiltonian path in the graph. Therefore Hamiltonian path problem is in $\mathsf{NP}$.

So in intuitive terms, $\mathsf{NP}$ is the set of problems that a given solution can be confirmed efficiently and $\mathsf{coNP}$ is the set of problems that a given solution can be refuted efficiently. For example, a refutation for a $TAUT$ instance is an assignment that makes the formula false.


$coNP$ and $\oplus P$? Let a non-deterministic machine have at most $2^{t+1}-1$ accepting paths (highest significant bit position is $t$ and lowest significant bit position is $1$).
I want to decide if the number of accepting paths $N_{accept}$ is $0$ or $>0$.
I can ask a $\oplus P$ oracle to decide if $2^t|N_{accept}$ and $2^{t+1}|N_{accept}$ as $MOD_{2^m}P=MOD_2P$ by https://complexityzoo.net/Complexity_Zoo:M#modkp.
There are three different scenarios

$2^t|N_{accept}$ and $2^{t+1}|N_{accept}$ in which case $N_{accept}=0$.

$2^t|N_{accept}$ and $2^{t+1}\nmid N_{accept}$ in which case $N_{accept}=2^t$.

$2^t\nmid N_{accept}$ and $2^{t+1}\nmid N_{accept}$ in which case $1\leq N_{accept}\leq2^t-1$.

So $N_{accept}=0\iff\oplus P$ oracle accepts twice.
Why would the above not place $coNP$ in $\oplus P$ or at least $NP^{\oplus P}$?

The result that $\mathrm{MOD}_{2^m}\mathrm P=\mathrm{MOD}_2\mathrm P$ only applies when $m$ is constant. Thus, your strategy only works if $t$ is constant, which is a trivial case. You would need it to apply to $t\approx n^c$. (Actually, the argument works for $m=O(\log n)$, but this is still not enough.)
Specifically, the reduction of $\mathrm{MOD}_{2^m}\mathrm P$ to $\mathrm{MOD}_2\mathrm P$ relies on the simple number-theoretic fact that
$$2^m\mid s\iff2\mid s\land2\mid\binom s2\land2\mid\binom s{2^2}\land\dots\land2\mid\binom s{2^{m-1}}.$$
If $s$ counts the number of objects satisfying some property, then $\binom s{2^r}$ counts the number of $2^r$-element sets of objects with that property.
That is, given a language $L\in\mathrm{MOD}_{2^m}\mathrm P$ of the form
$$w\in L\iff2^m\mid\#\{x<2^{n^c}:R(w,x)\},$$
where $n$ denotes $|w|$ and $R\in\mathrm P$, we can express $L$ as
$$w\in L\iff\forall r<m\ 2\mid\#\{(x_0,\dots,x_{2^r-1})\in[0,2^{n^c})^{2^r}:R_r(w,x_0,\dots,x_{2^r-1})\},$$
where
$$R_r(w,x_0,\dots,x_{2^r-1})\iff x_0<\dots<x_{2^r-1}\land\forall i<2^r\:R(w,x_i).$$
(These $m$ instances of $\oplus\mathrm P$ can be then combined to a single $\oplus\mathrm P$ predicate as $\oplus\mathrm P$ is closed under poly-time Turing reductions; in fact, even $\mathrm{\oplus P^{\oplus P}=\oplus P}$.)
As long as $m=O(\log n)$, the sequences $(x_0,\dots,x_{2^r-1})$ can be represented with $n^{O(1)}$ bits, and the predicates $R_r$ are computable polynomial time, but neither is true for larger $m$.


Show that boring boolean circuit belongs to NP-complete class We say that a boolean circuit is boring if it returns the same
  result for $>\frac34$ possible input, where we have $n$ input gates.
  Hence, boring circuit returns the same output ($0$ or $1$) for
  $>\frac34 2^n$ inputs.   Prove that checking if boolean circuit is boring is NP-complete

Can you help me? I have no idea how to start. I tried to reduce $3$-SAT but no result.

The problem is PP-hard. This means that unless the polynomial hierarchy collapses to NP, then deciding whether a circuit is boring is not in NP (and consequently is not NP-complete). The collapse follows from the fact that PP is closed under complement, so $\mathsf{PP=NP}$ implies $\mathsf{NP=coNP}$. We now show that deciding whether or not a circuit is boring is PP-hard.

Suppose $L\in PP$, then there exists a probabilistic polynomial Turing machine $M$ such that $x\in L \iff \Pr\left[M(x)=L(x)\right]>\frac{2}{3}$. Now consider the machine $M'$ which tosses two coins, if both output "heads" accept, otherwise execute $M$. If $x\in L$ then $M'$ accepts $x$ with probability $\frac{1}{4}+\frac{3}{4}\Pr\left[M(x)=L(x)\right]>\frac{3}{4}$. Now, let $C_x$ be the corresponding circuit for $M'$ on input $x$ (its inputs are the coins for $M'$), then $x\mapsto C_x$ is a reduction from $L$ to your problem, since $x\in L\iff C_x \text{ is boring}$. To see why, note that if $x\in L$ then $C_x$ accepts more than $\frac{3}{4}$ of the possible inputs, and if $x\notin L$ then $C_x$ accepts $\frac{1}{4}\le t\le \frac{3}{4}$ of the possible inputs.

In fact, your problem is PP-complete. To see why this language lies in PP, Let $L$ be the language of circuits who accept more than a $\frac{3}{4}$ fraction of their input, and $L'$ be the language of circuits who reject more than a $\frac{3}{4}$ fraction of their inputs. Clearly $L,L'\in PP$, and since PP is closed under union, deciding whether a circuit is boring, i.e is in $L\cup L'$, is in PP. Note that both here and in the above we used the fact that the constant in the definition of PP can be changed to any rational number.

If we want to avoid using closure properties of PP, then an argument along the following lines should work. Consider the machine $M$, which upon given an $n$-input circuit $C$, approximates the acceptance probability of $C$ by evaluating it on different uniformly distributed random length $n$ strings. Let $\hat{p}$ denote our evaluation. If $\hat{p}\ge\frac{1}{2}$, then $M$ evaluates $C$ on a random string and accept iff $C$ accepts, otherwise $M$ accepts iff $C$ rejects.
Let $E$ denote the event that $|p-\hat{p}|\le \frac{1}{4}$, where $p$ is the real acceptance probability of $C$. By evaluating $C$ on polynomially many strings, we can make sure that $\Pr\left[E\right]\ge 1-\frac{1}{2^{2n}}$. If $C$ is boring, then conditioned on $E$, $M$ obtained the right evaluation of the majority of $C$ and accepts with probability $>\frac{3}{4}$. Thus, if $C$ is boring $M$ accepts with probability $>\frac{3}{4}\left(1-\frac{1}{2^{2n}}\right)$. If $C$ isn't boring, then $C$ outputs either $0$ or $1$ with probability of at most $\frac{3}{4}-\frac{1}{2^n}$. Thus, regardless of our evaluation $\hat{p}$, $M$ accepts $C$ with probability of at most $\frac{3}{4}-\frac{1}{2^n}<\frac{3}{4}\left(1-\frac{1}{2^{2n}}\right)$, which puts our language in PP.


How append, prepend, and generally insertAt work in RRB-tree I read the paper about Relaxed Radix Balanced trees (RRB trees) and am trying to implement them. What I can't get is how insertion at an index should be performed step by step. Can anyone proficient in this data structure describe this procedure?

Currently there's no "magic trick" to do an insertAt for RRB-trees: It can be implemented by doing

concat(append(leftSlice(rrb, i), elt), rightSlice(rrb, i))

Append can (as I've shown in my thesis) be very efficient. If you don't want to focus on transients and tails, then chapter 5 explains how you modify the persistent vector append algorithm to work for RRB-trees. In short, you have to first find the path to walk, then walk and update it just as in the persistent vector, but in addition you have to update the slot sizes.

Prepend is simply a special case of concatenation.


Most Efficient Method To Determine Triangle Fill Values Based On Corner Values I have a triangle and the value of the pixel intensity at each of the three corners of the triangle.  I want to interpolate to find interpolated pixel intensities for a set of points inside the triangle.  How can I do this?

The method I've tried is to do an value determination based on the distance of that fill-in point from each of the corners.

As an example, here is a single triangle example, with three points described in the format of (Value, X, Y), though in practice all values might be floating point.

(1.78, 2337, 1955)
(2.95, 2342, 1948)
(1.12, 2347, 1941)

One very simple approach is to use a linear model.  Let $I(x,y)$ be the pixel intensity of the pixel at coordinates $(x,y)$.  We can fit to a linear model:

$$I(x,y) = \alpha x + \beta y + \gamma,$$

where $\alpha,\beta,\gamma$ are parameters to be determined.  If we are given the pixel intensity at each corner of the triangle, then we know the value of $I(x,y)$ for each corner point $(x,y)$.  Since a triangle has 3 corners, this gives us 3 linear equations in 3 unknowns.  We can solve this system of linear equations to find $\alpha,\beta,\gamma$, and then use this linear model to fill in the value of all other points.

In particular, if the $i$th corner is at $(x_i,y_i)$ and has pixel intensity (value) $v_i$, then we get a system of three equations:

$$\begin{align*}
I(x_1,y_1) &= v_1\\
I(x_2,y_2) &= v_2\\
I(x_3,y_3) &= v_3
\end{align*}$$

Expanding the linear model, this becomes

$$\begin{align*}
\alpha x_1 + \beta y_1 + \gamma &= v_1\\
\alpha x_2 + \beta y_2 + \gamma &= v_2\\
\alpha x_3 + \beta y_3 + \gamma &= v_3
\end{align*}$$

Here we have three unknowns ($\alpha,\beta,\gamma$) and the rest are known constants.  So, we can solve this system of linear equations for $\alpha,\beta,\gamma$.  This involves inverting a $3 \times 3$ matrix and then multiplying it by a $3$-vector, so it should be relatively efficient.

Once you have derived the parameters $\alpha,\beta,\gamma$, you can now evaluate the value $I(x,y)$ at any other point $(x,y)$ in the triangle (or on its interior).  This lets you interpolate the value at each fill-in point.

The approach I described above works for black-and-white images.  If you have a color image, you can interpolate independently for each of the 3 channels (R, G, and B; you might get better results if you work in a transformed color space, e.g., HSV, CIELAB, CIECAM02).

I recommend you take a look at barycentric coordinates, as they simplify the formulas for interpolation in a triangular mesh.

If you are familiar with interpolation for image processing, bilinear interpolation is a slight generalization of this approach, where you add a $\delta xy$ term to the linear model.  However, bilinear interpolation isn't applicable here, because it requires 4 points: 3 points isn't enough.

It's possible to come up with more sophisticated interpolation models.  For instance, you could fit a linear model to more than 3 points (e.g., taking the corner points of all adjacent triangles as well), and use ordinary least squares linear regression to find a best-fit linear model, weighting the corners of the adjacent triangles lower than the corners of the target triangle.  You could also build generalizations of bicubic interpolation, etc.

More generally, I recommend that you do a bit of research on "tetrahedral interpolation", as I believe that is the catch-phrase for the kind of problem you are asking about (or the generalization of it to 3 dimensions).


Is there any relation between Global minimum cut problem and Maximal independent set? I have simple undirected graph. I want to determine a size of minimum vertex cover, a size of maximal independent set and a size of a global minimum cut.

A minimum vertex cover is complementary to a maximum independent set. So, I can find one of this this and get both of them.

Is there any relation with global minimum cut? Or I have to find this size independent from other?

Minimum cut can be computed efficiently (you haven't explained what global minimum cut is, but presumably it reduces to minimum $s$-$t$ cut). Minimum vertex cover (probably) cannot. So any connection would be rather indirect. Minimum cut is related to another quantity, maximum flow, which is defined more generally for weighted directed graphs. Both quantities are equal due to the fundamental max-flow min-cut theorem (sometimes known as the min-cut max-flow theorem).


Why doesn't the recursion theorem prove there is an undecidable finite set? I created something similar to Sipser's proof for the undecidability of $A_{TM}$ (theorem 6.5), "proving" the undecidability of a set that must be finite. Presumably, it's wrong, but I can't figure out why for the life of me.

$A_R := \{\langle M \rangle | M = R \land M \text{ accepts "foobar"}\}$
Assume $D$ decides $A_R$. $R:=$ On any input:

By the recursion theorem, get own description $\langle R \rangle$
Run $D$ on $\langle R \rangle$
Do the opposite of what $D$ says. If it rejects, accept. If it accepts, reject.

$R$ contradicts what $D$ says about $R$. So $D$ can't be a decider. (i.e. If $D$ accepts $R$, $R$ should accept "foobar", but $R$ will reject all strings. If $D$ rejects $R$, $R$ should reject "foobar", but $R$ will accept all strings).

But because $A_R$ can only contain $R$, $A_R = \emptyset \lor A_R = \{\langle R \rangle\}$. Either way, it's finite, so $A_R$ is decidable.
So what's wrong with the first argument? A few ideas cross my mind:

I'm losing an important detail by making an informal argument.
Something odd in the recursive relationship between building $A_R$ and referencing $D$. (this could possibly be avoided by narrowing it to the subset of TMs with the length of R, which we could "guess" before R is created - and it would still be finite)
Logic shenanigans (a la the Liar Paradox)

But I just don't see exactly what the problem is.
Elaborating on my interpretation of the error for additional reference:
The argument looks like this:

Given an arbitrary decider for $A_R$, we can construct a TM $R$.
Given $R$, we construct $A_R$.
Then we can obtain a contradiction. So there is no decider for $A_R$.

That's circular, and hopefully more obviously wrong. And guessing the length of $R$, as previously suggested, doesn't work either - because an arbitrary decider has an arbitrary length.

Your argument "goes backwards."

Note that your definition of $R$ depends on $D$ (step $2$). This means you can't conclude that no machine decides $A_R$, merely that $D$ specifically doesn't.

Basically, what you've written looks like this:

CLAIM: there is some $x$ such that no $y$ does [task involving $x$].
PROOF: picking some $y$, we build an $x$ such that $y$ does not do [task involving $x$].

And this isn't valid.

It may help to consider an argument of the same "shape" but about a more concrete topic.

CLAIM: there is a natural number $n>1$ which isn't divisible by any prime $p$.
PROOF: fixing a prime $p$, let $n=p+1$. Then $n$ isn't divisible by $p$.

The subtle nature of decidability often makes questions about it appear more complicated than they are, and I think this is such a situation.

It's worth noting that the recursion theorem can be applied here to show something - specifically, that the $A_R$s are not uniformly decidable.

Specifically, suppose I have some total computable function $f$. By the recursion theorem I can whip up a machine $R$ such that $R$ behaves as you describe for $D=f(R)$, and so $f(R)$ cannot decide $A_R$. This means:

  While for each $R$ there is some $D$ which decides $A_R$, there is no computable way to find such a $D$ given $R$.

This isn't surprising - the same result follows more simply from the unsolvability of the halting problem - but it is an important example of how the recursion theorem can be used to prove non-uniform decidability results even when each of the languages in question is decidable.


Why do we assume that a nondeterministic Turing machine decides a language in NP in $n^k-3$ in Sipser's proof At page 277 of Sipser's Introduction to the Theory of Computation, a proof of the NP-completeness of SAT is given.

The following comment is made on the trace of some machine $N$ which can decide a language $A\in\mathrm{NP}$:

"Next, we take any language $A$ in NP and show that $A$ is polynomial time reducible to SAT. Let $N$ be a nondeterministic Turing machine that decides $A$ in $n^k$ time for some constant $k$. (For convenience, we actually assume that $N$ runs in time $n^k-3$, but only those readers interested in details should worry about this minor point.)"
(p. 277)

Interestingly, Levin's paper, Universal Search Problems, which discusses the search version of computation (in contrast to the decision version) states:

"Two function $f (n)$ and $g (n)$ will be said to be equal if there exists some $k$ such that:
\begin{equation}
f (n) \leq (g (n) +2)^k\  \textrm{and} \ g (n) \leq (f (n) +2) ^k.
\end{equation}
The term less than or equal is defined similarly."
(p.1 of the paper)

Levin is sometimes co-cited with Cook for the proof of the NP-completeness of SAT (Cook-Levin theorem).

So what are those $2$ and $3$ constants? Are they even related or was it just an intuition? In conventional big-O notation, we would have said $\pm O(1)$. But here, both authors take the time to specify an exact constant, and both are discussing the notion of polynomial-time reduction.

The tableau used in the proof has dimensions $n^k \times n^k$. The reason is that each row represents the contents of the tape, and the number of symbols on the tape cannot possibly be more than the runtime of the algorithm. However, in the proof, the first and last cell of each row is a # symbol, and each row also needs one cell to store the current state $q$ of the TM. Thus to be sure we are able to fit the entire contents of the tape and these 3 extra symbols in $n^k$ cells, we must say the runtime (and hence the space used on tape) is bounded by $n^k - 3$.


Doubts on the behavior of Unit Type in a type system I have a doubt about the Unit Type in the context of Type Theory and its use in different case scenarios.

To start with, a Unit Type can be seen as a nullary Product Type, namely Unit, with one only value term which is the empty tuple, (). Also, there exist a unique map from any type to the Unit.

Now, it happens that the use of the Unit Type goes beyond such trivial definition, and is in fact used in the definition of Algebraic Data Types, which are Sums of Product Types. Specifically, it is possible to represent the concept of an Enumerated Type using a Sum of Unit Types, e.g. in StandardML we might have:

datatype suit = HEARTS | CLUBS | DIAMONDS | SPADES

where HEARTS, CLUBS, DIAMONDS and SPADES are nullary Product Types and therefore all isomorphic to the Unit.

My doubt is the following: if there exist only one element of Unit, how can the type system distinguish between the four distinct instances used in the Sum Type above (five instances if we also consider the empty tuple...)?
I understand that they can be considered all equal to each other up to isomorphism, but they are extensionally different and in fact, even by considering only the suit we are supposed to pattern-match on them...

The short answer is that isomorphic types are not equal, despite behaving identically, and so the type system can distinguish between them. In a nominal type system, like the one you describe, types are essentially identified by their names, even if they are structurally equivalent. This is the case for the five unit types you describe: they are structurally equivalent, but nominally unequal, and so they are treated as distinct.

Note that the pattern matching aspect is orthogonal: you can think of the five unit types as existing in isolation. In most type theories, you can take the sum of any two types, even two that are (nominally) equal, e.g. Unit + Unit. You will still be required to pattern match, and will have two cases: the left Unit and the right Unit. The nominal aspect is unimportant, although many programming languages will use the names to distinguish between the different cases like this, instead of the indices of the summands (in particular, in languages where you are only allowed to take sums of distinct nominal types, like Standard ML).


How to minimally extend a digraph such that all nodes are on a cycle? Let's say we have a directed graph with $n$ nodes and $m$ edges. For each node we want to make path that will start from this node, possibly traverse some other nodes and finish in the same node, in other words we want to make a cycle through each node. It is allowed to add edges that start and finish in the same node.

We want to use minimum number of edges.

Let's for example consider the following graph. We can add edges: $(1,1),(2,2),(3,3),(4,4)$. But that will cost us to add 4 edges, and we can make the cycles with adding only one edge $(4,1)$.

I think that first we should find all the paths in the graph, and then link the last node with the first node, this will allow us to minimize the added edges, and surely will make all the nodes in the path linked in the cycle.

But the problem is find all the paths, I cannot think of the algorithm that will find us all pairs of paths, also the problem is if there is more than one path between the first and the last nodes, please give me some hints on how to solve this problem.

Also, I think that finding all paths in the graph is $NP-hard$ and it may be really slow, but the number of nodes is small, less than 20, so even solution of time complexity $O(2^N)$ are good.

Find all the strongly connected components (SCC) of the original
graph.
Replace each SCC by a single node - the resulting graph $G'$ will be acyclic.
Find all the sources and sinks in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
Match sinks with sources using algorithm by Eswaran and Tarjan (see here), corrected by Raghavan (see here), then add $max(m,n)$ edges for all the matched (sink, source) pairs.
Replace each node, representing SCC, by this SCC.

This approach will give you a strongly connected graph provided that the original graph is connected. Your requirement to have all the nodes belonged to some cycle is more weak - for example, a set of SCC's, not connected at all or connected by single edges, satisfies your goal definition.

However, it's unclear if this more weak requirement will allow you to decrease the number of additional edges compared to the number of additional edges, given by the algorithm, described here.


Can any algorithm efficiently be implemented as a SIMT problem? Many algorithms can be implemented more efficiently using SIMT instructions (e.g. CUDA) than using sequential instructions.

Excluding overhead due to hardware limitations (specifically, memory copy times when using a GPU) - are there algorithms whose efficiency can only be made worse in a SIMT model? By "efficiency," I mean here the total number of elementary operations / # parallel processing elements.

(Assume that each individual compute element in the SIMT model is (made to be) exactly as fast as the single compute element in the sequential model. Therefore, computing time is the same as the number of elementary operations.)

Asked another way, can any algorithm be made at least as efficient using SIMT instructions than it could using sequential instructions? Again, I'm purely talking about computing "time" here - not set up / memory copies (which are the typical reason why you wouldn't use a SIMT processor for a highly sequential problem AFAIK).

No, efficiency cannot be strictly worse, for trivial reasons.  For instance, you can have all $n$ threads independently compute the same thing -- each doing the same thing that the sequential computation would have done.

This is not very interesting or useful in practice, for a number of reasons: (1) in practice, in SIMT architectures each individual compute element is typically less powerful than the compute element in a sequential system; (2) we care not just about compute time but about energy usage, and wasting energy on pointless computation would be, well, pointless.

At the same time, it is true that there are computational tasks that are inherently sequential: they cannot be sped up on a parallel processor (including a SIMT machine).  See, e.g., Which algorithms can not be parallelized?, https://crypto.stackexchange.com/q/606/351.