texts: Do the time and space complexities of a language depend on the Turing machine which is its recognizer?

texts:
From Ullman and Hopcroft's Introduction to automata theory, languages, and computation

  Consider the off-line Turing machine M of Fig. 12.1. M has a read-only
  input tape with endmarkers and k semi-infinite storage tapes. If for
  every input word of length n, M scans at most S(n) cells on any
  storage tape, then M is said to be an S(n) space-bounded Turing
  machine, or of space complexity S(n).
  The language recognized by M is also said to be of space complexity S(n).

  Consider the multitape TM M of Fig. 12.2. The TM has k two-way
  infinite tapes, one of which contains the input. All tapes, including
  the input tape, may be written upon. If for every input word of length
  n, M makes at most T{n) moves before halting, then M is said to be a
  T{n) time-bounded Turing machine, or of time complexity T(n). The
  language recognized by M is said to be of time complexity T(n).

If I am correct, a language can be the one recognized by several Turing machines.

Do the last sentences in the two paragraphs assume that for a language, all of its recognizer TMs have the same time complexity and the same space complexity?

Is the assumption true?
If the assumption is not true, do the sentences imply taking supremum of the complexities over all of the recognizer TMs of the language?

Thanks.


texts:
So the problem is, given some set $M = \{x_1,x_2,\ldots,x_n\}$ and a set of subsets $S = \{S_1, S_2, \ldots, S_m\}$ where $S_i \subseteq M$. We want to find some set $X \subseteq M$ such that $|X| \le k$ and $X \cap S_i \neq \emptyset$ for all $S_i \in S$.

My solution, I would take some set $M = \{x_1,x_2,x_3,x_4\}$ and suppose $S_1 = \{x_1,x_2\}$, $S_2 = \{x_2,x_3\}$, $S_3 = \{x_4\}$. I would then transform this to a SAT instance to get:

$\phi = (x_1 \vee x_2) \wedge (x_2 \vee x_3) \wedge (x_4)$

Clearly if $\phi$ is satisfiable then there exists some $X \subseteq M$ however this does not guarantee that $|X| \le k$.

So my question is, how can I reduce this problem further so that $|X| \le k$ in polynomial time?

EDIT

I realized there may be an easier way to reduce this to the set-cover problem but need confirmation that my idea is correct.

Will post a new question containing this.


texts:
How is tamper-proofing of software evaluated for effectiveness?

I've been implementing a few algorithms listed within Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection. The algorithms include tamper-proofing of software by means of introspection (or computing a hash at runtime over some region of code).

However, nothing is said about the evaluation of such tamper-proofing algorithms: How are they compared to each other and how are their effectiveness measured?

Searching Google, I've come across few articles discussing the subject. One of the articles made an emperical evaluation, where they asked "hackers" to break their implementation and then measured the time taken.

Does anyone know how to evaluate tamper-proofing at a theoretical level?


texts: Does a Turing machine really need an infinite tape

texts:
Turing machines are usually described as having an infinite tape (i.e. a tape with infinitely many memory locations), but I think it only needs to have a  tape that has a sufficient but finite number of memory locations for the problem it's working on, (although, of course, it is unknown in advance how many locations will be needed.) Am I right?

Alternative question: if and when a Turing machine halts, has it only used a finite portion of its tape?


texts:
I have a question regarding the redundancy of Huffman coding. I know that for a general prefix code we have the following inequality:

$$ H(X) \le R \le H(X) + 1 $$

$R$ being the rate (average codeword length) and $H$ is the entropy. Based on this relation, how can we conclude that Huffman coding is very inefficient if entropy of the source is much smaller than 1 bit/symbol?


texts:
Let PCPk be a version of PCP where we can use at most k copies of each domino to create correspondences. Prove that for any finite k = 1, 2, 3 … PCPk is decidable.
I know this kind of PCP is called bounded PCP which is decidable. Does anyone know how to prove the decidability?


texts: How to write grammar production rules to describe recursive structures?

texts:
I'm trying to describe a data structure by production rules. The structure is recursive; say a list of type $A$ made of elements of type $A$ or $B$.

Writing the grammar, I build this:

  $(S \rightarrow AS|ε)$
  $(A \rightarrow AA|bA|ε)$

where $b$ is a terminal representing element $B$ of my list.

The production $A \rightarrow AA$ got me a little baffled... is there something right? Thank you.


texts: The padding argument in the proof of NTIME(n) ⊆ DTIME(n^1.2) implies Σ2-TIME(n^8) ⊆ NTIME(n^9.6)

texts:
In "Computational Complexity, A modern approach", Arora & Barak proof the following claim (Claim 5.11.2):

  Suppose that $\mathsf{NTIME}(n) \subseteq \mathsf{DTIME}(n^{1.2})$. Then $\Sigma_2$-$\mathsf{TIME}(n^{8})  \subseteq \mathsf{NTIME}(n^{9.6})$,

which they prove in the following way:

If $L \in \Sigma_2$-$\mathsf{TIME}(n^8)$, then $\exists$ TM $M$ which runs in time $O(|x|^8)$ s.t.
$x \in L \leftrightarrow \exists u \in \{0,1\}^{c|x|^8} \forall v \in
\{0,1\}^{d|x|^8} M(x,u,v) = 1$
But if $\mathsf{NTIME}(n) \subseteq \mathsf{DTIME}(n^{1.2})$, then

  by a simple padding argument, we have a deterministic algorithm $D$ that on inputs $x, u$ with $|x| = n$ and $|u| = cn^8$ runs in time $O((n^8)^{1.2}) = O(n^{9.6})$ and returns $1$ iff there exists some $v \in \{0,1\}^{dn^8}$ such that $M(x,u,v) = 0$

I struggle to see what this "simple padding argument" might be? That is, how do we get respective deterministic algorithm $D$ if we have the TM $M$?


texts:
Maybe my question doesn't make sense, because I lack some more thorough understanding, but I was curious if arithmetic was Turing complete?

As I understand it, a "model of computation" is a mechanism where you can compute outputs from inputs. Thus a "computation" is just a mapping from inputs to outputs.

So if say the universe of possible inputs and outputs is: 1 and 2. This would be all possible computations:

1 -> 1
1 -> 2
1 -> 1,2
1 -> 2,1
2 -> 1
2 -> 2
2 -> 1,2
2 -> 2,1
1,2 -> 1
1,2 -> 2
1,2 -> 1,2
1,2 -> 2,1
2,1 -> 1
2,1 -> 2
2,1 -> 1,2
2,1 -> 2,1

Now, I think this isn't even technically the full set, because the full set would be infinite, since I could have repeated inputs and outputs like 1,1 -> 2,2,1,1. But at least this is the general gist which I understand.

And in my "model of computation", I should be able to say, apply the computation X to some inputs, where X is one of the above mapping, and get back the corresponding outputs.

So from this, I understand that the Turing Model is proven to be able to map all inputs to outputs over the universe of non complex numbers.

So my question is, would arithmetic be Turing Complete in its ability to map inputs to outputs? Or is there some mappings that can not be formulated using arithmetic, but can using the Turing model?


texts: Confusion related to this algorithm about finding the orientation given 3 points

texts:
I have a confusion related to an algorithm for finding the orientation given three points, i.e., determining whether one line is clockwise or counter-clockwise of another.

Let's say the points are $P_1=(x_1,y_1)$, $P_2=(x_2,y_2)$, $P_3(x_3,y_3)$. The algorithm says

Let the slope of line $P_1P_2$ be $m_1$ and slope of $P_2P_3$ be $m_2$.
If $m_2 > m_1$, the orientation is counterclockwise and if $m_1 > m_2$ it is clockwise.

However lets say the points are $(0,0)$, $(4,4)$ and $(2,4)$. This give $m_1=1$, $m_2=0$. The orientation is counter clockwise but $m_2 < m_1$. So I am wondering if there is any issue with the algorithm.

Any suggestions?


texts: Definition of $\Theta$ for negative functions

texts:
I'm working out of the 3rd edition CLRS Algorithms textbook and in Chapter 3 a discussion begins about asymptotic notation which starts with $\Theta$ notation. I understood the beginning definition of:

$$\Theta(g(n)) = \{ f(n)\,|\, \exists\, c_1, c_2 > 0, n_0 \in \mathbb{N}: 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)\ \ \forall n \geq n_0\}$$

But then on the next page the text says that:

  The definition of $\Theta(g(n))$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever $n$ is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large $n$.) Consequently, the function g(n) itself must be asymptotically nonnegative, or else the set $\Theta(g(n))$ is empty.

That last part about the how if the function is negative the set $\Theta(g(n))$ is empty and the general requirement of a positive function is sort of confusing. Can anyone out there clarify this definition for me and what it means, possible with an example, it would be much appreciated.


texts: Is there a graph theory textbook that covers treewidth thoroughly?

texts:
Can someone recommend a graph theory textbook that covers treewidth thoroughly?
Something that focuses on the graph-theoretic structure of bounded treewidth graphs rather than solving problems on them.  Don't need the strongest/newest results but would prefer something that
Preferably something that covers sublinear treewidth of planar and minor free graphs.


texts:
I was reading page 6 of https://www.cs.cmu.edu/~reids/planning/handouts/Linear.pdf

And it is not clear to me that the STRIPS algorithm necessarily terminates.

Namely if we have a simple goal sg on the stack, and CANNOT find an operator O whose addlist includes all of sg, how do we go about picking operators? At this point it seems very easy to create counterexamples that cause the algorithm to loop, regardless of what heuristic one selects.

Furthermore, if we have multiple operators each of whose addlist includes all of sg, how do we pick the best operator (or is the choice arbitrary?).


texts: Why is part of speech tagging is closely related to word sense disambiguation?

texts:
It's written here Word Sense Disambiguation: A Structured Learning Perspective:

  2.1 Basics of Word Sense Disambiguation

  ...the POS is usually provided before WSD. POS tagging is closely related to WSD, and POS tagging is a well-studied problem with accuracy over 95%, thus the separation of POS tagging from WSD can fully expose the hardest core of WSD.

The best explanation for the proposition in boldface inside the blockquote I could find on google is the following picture on book Neural Representations of Natural Language:

Nonetheless, that book explain the relationship between POS tagging and other word sense problems and not to Word Sense Disambiguation.

Please, explain the relationship between POS (part-of-speech) tagging and WSD (word sense disambiguation).


texts:
The proof that $IP \subseteq PSPACE$ is done by considering by game tree of the interactions between the prover and the verifier; this tree is polynomial in depth and each message is polynomial in length, so the tree can be explored in a DFS like fashion to simulate an optimal prover in PSPACE.
Why can't the same be done for MIP? Proofs that $MIP \subseteq NEXP$ usually show that the multiple provers can be simulated by non-deterministically guessing a strategy for each, but why can't you just simulate the tree of interactions as in the single-prover case?


texts:
This is just a question for fun and specifically for those who have read the reference pervasively.

I have been reading the work of Knuth's The Art of Computer Programming and struggling and having a lot of fun with its exercises. I was very impressed that Fermat's Last Theorem had a difficulty of 45 in Knuth's difficulty scale.

I was wondering, if anyone of you have seen exercises with rank ≥50.

Perhaps a more interesting question, what is the current status of such problems nowadays!?


texts: Choosing correct action in bottom up parsing

texts:
Using grammar:

$
S \to aABe \\
A \to bcA \mid c \\
B \to b
$

to bottom parse a string $abcccde$, the course of action would be:
$
\begin{array}{c|c|c|c}
\hline
Step & Stack    & Input    & Action               \\ \hline
1    & \epsilon & abccde   & Shift                \\
2    & a        & bccde    & Shift                \\
3    & ab       & ccde     & Shift                \\
4    & abc      & cde      & Shift                \\
5    & abcc     & de       & Reduce \, by \, A \to c    \\
6    & abcA     & de       & Reduce \, by \, A \to bcA  \\
7    & aA       & de       & Shift                \\
8    & aAd      & e        & Reduce \, by \, B \to d    \\
9    & aAB      & e        & Shift                \\
10   & aABe     & \epsilon & Reduce \, by \, S \to aABe \\
11   & S        & \epsilon & Done
\end{array}
$

My questions are:

At step 4, why do we choose to Shift rather than to reduce $ A \to c$.
How would a parser decide which is correct to choose?


texts: I was looking at Gödelization in Theory of Computation course. I could understand the Gödel numbering concepts, but couldn't understand its importance in Theory of Computation. Could anyone please point to some good materials or point out its importance.


texts: Are physical laws uncomputable in any type of computation (according to this article)?

texts:
It seems that this article (https://arxiv.org/pdf/1312.4456.pdf) proposes that laws of physics are uncomputable (i.e., they could not be reproduced on a computer), but I'm not sure about it.

In some part of the article it says:

  If
  we expand the set of computational devices that we use to define computational complexity,
  then the consequences of the known laws of physics can in principle be elaborated in
  polynomical [sic] time on classical and quantum computers.

  If we restrict our attention to laws whose consequences can be evaluated in polynomial
  time, then the problem of finding concise expressions of physical laws is no longer
  uncomputable.

So, what is it saying? That laws of physics are uncomputable? That laws of physics could not be reproduced in a computer? That laws of physics could not be reproduced in any type of computer?

Also, in the conclusions it says:

  This chapter reviewed how uncomputability impacts the laws of physics. Although
  uncomputability as in the halting problem arises from seemingly esoteric logical paradoxes,
  I showed that common and basic questions in physics have answers that are uncomputable.
  Many physical systems are capable of universal computation: to solve the question of
  whether such a system has discrete or continuous spectrum in a particular regime, or
  whether it is gapped or gapless, requires one to solve the halting problem. At a more
  general level one can think of the all scientific laws as providing concise, easily unpacked
  descriptions of obserbational [sic] and experimental data. The problem of finding the most
  concise description of a data set is uncomputable in general, and the problem of finding
  the most concise description whose predictions are easily evaluated is NP-complete.

So, what can we conclude from this? Also, what does it exactly mean that "finding the most concise description whose predictions are easily evaluated is NP-complete"?


texts: What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?


texts: How to prove that a language is not context-free?

texts:
We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free.

How do I show the opposite, though? My TA has been adamant that in order to do so, we would have to show for all grammars (or automata) that they can not describe the language at hand. This seems like a big task!

I have read about some pumping lemma but it looks really complicated.


texts: Series where each term is square of previous

texts:
The problem statement is as follows:-

  In a court case, a judge cited a court of contempt and ordered a fine of $2 for first day.
  On subsequent days, the fine would be equal to the square of the previous day's fine.
  e.g. 2, 4, 16, 256 and so on.
  Find out:-

  a) What would be the fine on day $n$?

  b) How many days would it take the fine to reach $D$ dollars?

A big Oh answer would be appreciated.


texts: What happened if we implement quicksort without tail recursion?

texts:
On Wikipedia, it said that

  The in-place version of quicksort has a space complexity of $\mathcal{O}(\log n)$, even in the worst case, when it is carefully implemented using the following strategies:

    in-place partitioning is used
    After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most $\mathcal{O}(\log n)$ space. Then the other partition is sorted using tail recursion or iteration, which doesn't add to the call stack.

Below is naive quick sort:

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

Below is tail recursion quick sort:

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

Algorithms above are based on this link

What if we just use in place partitioning? Is it not enough to make quicksort having space complexity of $\mathcal{O}(\log n)$?

Below is what I understand of stack call of quicksort. Do I misunderstand it?

Suppose I have sequence of number: $\{3, 5, 2, 7, 4, 1, 8, 6\}$. I use in place method in this case.

input    : 5   3   2   7   4   1   8   6
partition: 3   2   4   1  (5)  7   8   6
stack 1  : 2   1  (3)  4
stack 2  : 1  (2)
stack 3  : 1                               - stack 3 removed
stack 2  : 1  (2)                          - stack 2 removed
stack 1  : 1   2  (3)   4
stack 2  :              4                  - stack 2 removed
stack 1  : 1   2  (3)   4                  - stack 1 removed
input    : 1   2   3   4  (5)  7   8   6
stack 1  :                    (6)  7   8
stack 2  :                        (7)  8
stack 3  :                             8   - stack 3 removed
stack 2  :                        (7)  8   - stack 2 removed
stack 1  :                    (6)  7   8   - stack 1 removed
input   : 1   2   3   4   5   6   7   8 -> sorted

We need $3$ stacks at most, which is $$\log(n) = \log(8) = 3$$

If what I told above is correct, the worst case with that method is $n$, which is happened when the pivot is the minimum or maximum

input    : 5   3   2   7   4   1   8   6
stack 1  :(1)  5   3   2   7   4   8   6
stack 2  :    (2)  5   3   7   4   8   6
stack 3  :        (3)  5   7   4   8   6
stack 4  :            (4)  5   7   8   6
stack 5  :                (5)  7   8   6
stack 6  :                    (6)  7   8
stack 7  :                        (7)  8
stack 8  :                             8
stack 7  :                        (7)  8
stack 6  :                    (6)  7   8
stack 5  :                (5)  6   7   8
stack 4  :            (4)  5   6   7   8
stack 3  :        (3)  4   5   6   7   8
stack 2  :    (2)  3   4   5   6   7   8
stack 1  :(1)  2   3   4   5   6   7   8
input    : 1   2   3   4   5   6   7   8 -> sorted

we need $8$ stacks, which is $n$

That's why in place partitioning is not enough. But if I am correct, what makes it different using tail recursion?

And also, anyone can give pseudo code for iteration instead of tail recursion?


texts: How to approach backtracking when using immutable types (Python)?

texts:
In Python when we are building a recursive algorithm that uses backtracking a mutable type such as a list is great to use. It can be modified at each call in our recursion tree, then returned back to it's original state once all children have been recurred on. See the image below for an example.

However, when using a mutable type such as an integer this is impossible. If we try to 'modify' an integer by using a reference to it in memory a new integer will be created. This makes it impossible to backtrack with immutable types.

What is the best practice way around this? We could store the integer in a list like this [0] but then we would be using a list data structure for a very non list-like purpose which isn't ideal in my books.

Any ideas would be appreciated.


texts: What does "monotonicity" mean in the context of mutability

texts:
I'm reading The Rust Programming Language and found the following passage:

  Remember that writing to a struct is not an atomic operation, and many
  functions like vec.push() can reallocate internally and cause unsafe
  behavior, so even monotonicity may not be enough to justify
  UnsafeCell

It just popped out of nowhere in the book and I've had a hard time online trying to find what it exactly means in this context. Too much information is about the concept of "monotonicity" of mathematical functions, which I already knew but is apparently not very helpful.

I only seemed to find this article that talks about it.

  Now, in addition to respecting equality in the obvious way, I also include the stipulation that a functional program must respect the monotonicity of observations. What do I mean by this? It must be that once you have observed something at a point in time, then that will not cease to be evident in the future. This is analogous to the monotonicity property in Kripke or Beth semantics.

However this is also quite abstract and I'm not sure it talks about the same thing either.


texts: Line-search does not guarantee convergence so how to use it?

texts:
Line-search/backtracking in gradient descent methods essentially boils down to picking the current estimate $\theta_n$ (which depends on the stepsize $\gamma$ and the prior estimate $\theta_{n-1}$) by performing line-search and finding the appropiate $\gamma$.

This search depends on a 'sufficient descent' criterion.

It can happen that the sufficient descent criterion simply is not going to be satisfied for any reasonable $\gamma$. That is, you are at a part in your search for the optimal point where no matter how small a step-size you take, you are not getting sufficient descent.

Here, line-search would get stuck in an infinite loop (or, a near-infinite loop: the sufficient descent criterion might be satisfied eventually due to numerical errors)

So, how should this be fixed? One option is to omit line-search completely: fixing $\gamma$ to be a constant, you will eventually converge if $\gamma$ is small enough.

A second option is to do line-search for an optimal $\gamma$, but only for a small amount of time (say, 20 iterations). If you haven't found a optimal $\gamma$ by then, then just take any fixed step and hope you get back towards convergence.

What do people do?


texts: Information content of computational problems

texts:
The notion of low information content is used to describe sparse sets and tally sets in complexity theory. Such sets can not be $NP$-complete unless $P=NP$. I am not aware of a formal information-theoretic definition which I hope would lead to insights into the phenomena of complexity hierarchy inside $NP$.

  What are the barriers to measuring the information content of computational problems? ( perhaps using ideas inspired by notions like topological entropy or Shannon probabilistic entropy)

Note that I am interested in worst-case computational information content. The term low information content probably motivated by the widely believed conjecture that sparse sets can not be $NP$-complete ( unless $P = NP$).


texts: Process Synchronization: Dekker's algorithm

texts:
This Screenshot is taken from William Stalling's Operating Systems book.
My doubt is that Bounded wait is not satisfied by this solution.

For example: P0 and P1 both want to enter critical section and set their flags to true.

flag[0] = true

flag[ 1] = true

Both p0 and p1 enter while loop, p0 wins the race process P1 sets its flag to false

now flag[ 1]= false

Process P0 goes into Critical Section, comes out, sets turn = 1 and flag[0]=false.

Now actual problem starts from here:

Process P1 comes out of infinite while loop and before i could set flag[ 1] to True from False, it gets preempted.

Now Process P0 can go any number of times in Critical section because Flag[ 1] is False.

Conclusion: Process P1 tried to get access to critical section but because of bad solution it did set its flag to False to give path to Po and now stuck for infinite time.

hence B.W is not satisfied!


texts: Verify correctness of quantifier elimination, using SAT

texts:
Let $x=(x_1,\dots,x_n)$ and $y=(y_1,\dots,y_n)$ be $n$-vectors of boolean variables.  I have a boolean predicate $Q(x,y)$ on $x,y$.  I give my friend Priscilla $Q(x,y)$.  In response, she gives me $P(x)$, a boolean predicate on $x$, and she claims that

$$P(x) \equiv \exists y . Q(x,y),$$

or in other words, that

$$\forall x . [P(x) \Leftrightarrow \exists y . Q(x,y)].$$

I would like to verify her claim somehow.  How can Priscilla help me verify this claim?

You can assume that both $P$ and $Q$ are represented as CNF formulas, and that they're not too large (polynomial size, or something).

In an ideal world, it'd be awesome if I could reduce the problem of verifying this claim to SAT: I have a SAT solver, and it'd be great if I can use the SAT solver to verify this claim.  However, I'm pretty sure that it's not going to be possible to formulate the problem of verifying this claim directly as a SAT instance; testing the validity of a 2QBF formula is almost certainly harder than SAT.  (The $\Leftarrow$ direction is easy to formulate as a SAT instance, but the $\Rightarrow$ direction is hard because it inherently involves two alternating quantifiers.)

But suppose Priscilla could give me some additional evidence to support her claim.  Is there some additional evidence or witness Priscilla could give me, which would make it easy for me to verify her claim?  In particular, is there some additional evidence or witness she could give me, which would make it easy for me to formulate the problem of verifying her claim as an instance of SAT (which I can then apply my SAT solver to)?

One unusual aspect of my setting is that I'm assuming (heuristically) that I have an oracle for SAT.  If you like complexity theory, you can think about it this way: I am taking the role of a machine that can compute things in $P^{NP}$ (i.e., in $\Delta^P_2$), and I'm looking to verify Priscilla's claim using an algorithm in $P^{NP}$.  My thanks to mdx for this way of thinking about things.

My motivation/application: I'm looking to do formal verification of a system (e.g., symbolic model checking), and a key step in the reasoning involves quantifier elimination (i.e., starting from $Q$, obtain $P$).  I'm hoping for some clean way to verify that the quantifier elimination was done correctly.

If there's no solution that works for all possible $P,Q$, feel free to suggest a solution that is "sound but not complete", i.e., a technique that for many $P,Q$ lets me verify the claimed equivalence. (Even if it fails to verify the claim on some $P,Q$ that do satisfy the claim, I can still try this as a heuristic, as long as it never inappropriately claims to have verified a false claim.  On any given $P,Q$, it might work, or it might not; if it doesn't work, I'm no worse off than where I started.)


texts: Let’s make a big list of algorithms relying on abstract algebra. This will help us see how ubiquitous algebra is in algorithm design. I’ll start with two: one is the General Number Field Sieve, the other is Babai’s graph isomorphism algorithm.


texts:
I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal.
More formal definition of the problem from a Wikipedia article on KPs:

If all the profits are 1, we will try to maximize the number of items which would not exceed the knapsack capacity:
maximize $\sum_{j=0}^n x_j$
subject to $\sum_{j=0}^n w_jx_j \leq W$,
$x_j \in \{0, 1\}, \forall_j \in \{1, ..., n\}$

I skimmed through Knapsack Problems book (Kellerer et al', 2004) that is referenced by that Wikipedia article but couldn't find that particular problem.
I also saw some posts about this exact problem with no good answers:

Knapsack with same value
Knapsack problem with all profits equal to 1

The answer to the first post mentions Capital Budgeting problem, but the provided link doesn't discuss the case where all profits (values) are equal, which I believe can be better optimized due to its special case.
The answer to the second post mentions a naive solution in which a greedy algorithm picks minimum weight items at each step until no more items fit in the knapsack. This requires knowing the order of items by weight, which results in $O(n\log{n})$ solution.
Is there an algorithm with a better upper bound (e.g. linear time)?


texts: Church-Turing thesis and hypercomputation?

texts:
The Church-Turing is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource limitations, if and only if it is computable by a Turing machine.
In wikipedia (https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis), explains some of the philosophical interpretations of it:

The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the strong Church–Turing thesis, or Church–Turing–Deutsch principle, and is a foundation of digital physics.

The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a hypercomputer. For example, a universe in which physics involves random real numbers, as opposed to computable reals, would fall into this category.

The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all quantum mechanical events are Turing-computable, although it is known that rigorous models such as quantum Turing machines are equivalent to deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.) John Lucas and Roger Penrose have suggested that the human mind might be the result of some kind of quantum-mechanically enhanced, "non-algorithmic" computation

The third interpretation is the one that seems more interesting to me. I know that there is evidence against the possibility of hypercomputation, but it is still interesting to consider the universe as a hypercomputer.
However there is no reference of who developed that interpretation.
So my questions are: Who did develop that interpretation? Is there any paper about it?


texts: What does Stroustrup mean by 7/8ths of MIPS being in the vector units?

texts:
In his article Software Development for Infrastructure Stroustrup states the following:

  Hardware improvements make the problems and costs resulting from
  isolating software from hardware far worse than they used to be. For a
  typical desktop machine,

  3/4ths of the MIPS are in the GPU;
  from
  what’s left, 7/8ths are in the vector units; and
  7/8ths of that are
  in the “other” cores.

  So a single-threaded, nonvectorized, non-GPU-utilizing application has access to roughly 0.4 percent of the compute power available on the device (taken from Russell Williams).

Now I understand the GPU and threading issues of performance. But since threading and vectorization are mentioned as separate things, I would like to know what does it exactly mean when you say that vector units are X% of the computing power.


texts: What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence?

texts:
I am trying to wrap my head around how dynamic programming helps avoid all possibilities that are exponential after reading Chapter 8 NP-complete problems of Algorithms by Dasgupta et al. where it says:

So far in this book we have seen the most brilliant successes of this quest, algorithmic techniques that defeat the specter of exponentiality: greedy algorithms, dynamic programming, linear programming (while divide-and-conquer typically yields faster algorithms for problems we can already solve in polynomial time).

Going back to Chapter 6 Dynamic programming, I followed along the longest increasing subsequence problem that this video also shows how to solve. It seemed to me that we were considering all other choices in the solution for the sequence $3, 4, -1, 0, 6, 2, 3$, but only did this with $n^2$ time.
What are the other possible subsequences that would reveal that this problem is exponential in nature without dynamic programming? I can see that in the 0-1 Knapsack problem there are $2^n$ possibilities to consider but can't see the exponential counterpart of the longest increasing subsequence problem.


texts:
I have the following problem:

  Consider the MAX-3-SAT problem: given a Boolean function in
  Conjunctive Normal Form (CNF) determine the maximum number of clauses
  that can be satisfied. Prove that this problem is NP-hard.

I know that I'd have to reduce 3-SAT to MAX-3SAT, but I'm pretty lost on how that would work. The related decision problem I figured would be, given clauses and a number k, is there an assignment satisfying at least k of the clauses?


texts: What is the difference between halting, accepting, and deciding in the context of Turing machines?

texts: Does accepting mean that the TM will read and recognize a char from the cell it's currently reading from? And is it the case that a TM halts iff the input is decidable?


texts: Does stay put TM recognizes same languages as standard TM

texts: I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or symbols). I am trying to figure that out.. But so far, no luck. I think the key here is "recognizes" rather than "decides"? How do i prove this? Thanks


texts: Can an instruction with a dependency read the register in same cycle as it's being written?

texts:
I'm learning about superscalar processors and struggling with it a bit. I wrote an assembly program and now must move it through in-order in-issue completion and I have a question about instructions as they move through the latter stages of the pipeline.

I have two instructions I1 and I2. I1 performs an operation on R1 and R2 and then loads the result in to R1. I2 needs read the new result of R1 and then overwrite R1, but obviously cannot do so until R1 is finished, otherwise I1 will be incorrect. At what point will I2 be able to correctly read the new result of R1? While I1 is in the WB stage or once I1 has finished the WB stage?

Thanks! I also realize this may not be an ideal design, but it's what I have to work with. Also, if this is not CS related and belongs in a different stack exchange, please move.


texts: Whic representation of graph is preferred, anjacency matix or adjacency list?

texts:
I have a graph in which vertices are 100 and edges are more than 300. If I want to represent this graph in either adjacency matrix or adjacency list, which graph representation will be preferred?

My effort:

I have read several articles. In this article, I have found that the comparison should be done in the following criteria:

1) Terms of space and time.
2) how long it takes to determine whether a given edge is in the graph?
3)  how long it takes to find the neighbors of a given vertex.

So for the above question, I have found an adjacency matrix is the best solution. Is my assumption is correct? Please enlighten me.


texts: Categorising problems into complexity classes

texts:
Am I correct in saying that there are two ways to categorise a problem in complexity theory:

Find an algorithm that solves it. If the algorithm runs in polynomial time, then we can put it into P-class. If not, then we can put it into EXP.
Provide a reduction that this problem is no hard than another problem, to which we know the complexity class for.

If I cannot find a reduction and I do not have an algorithm, what is the "default" complexity class? I'm guessing it would be in the class of problems which cannot be solved until we find an algorithm.


texts:
Is every language with a finite number of strings regular?
Is the language of all strings regular?

I am new to this topic and got confused. Can any one please help me with this?


texts: Complexity for finding a ball that maximizes the number of points lying in it

texts:
Given a set of points $x_1, \ldots, x_n \in \mathbb{R}^2$ and a radius $r$. Which is the complexity of finding the point with higher number of points at a distance smaller than $r$. E.g the one that maximizes $\sum_{i=1}^n \mathbb{1}_{\|x - x_i\| \leq r}$?

A brute force algorithm would be to go over every point and count the number of points that are at distance smaller than $r$. That would give a complexity of $\mathcal{O}(n^2)$.

Is there a better approach?


texts: Computability - The language of all strings of even length

texts:
Define a language $L$ as follows:
$$L = \{\langle M \rangle \in \{0, 1\}^* | M\text{ is a TM that halts on all strings of even length} \}$$

I can prove that $L$ is not decidable/recursive, but is it recognisable/recursively enumerable? My intuition is that $L$ is unrecognisable because suppose there exists a TM $N$ that recognises $L$, $N$ would have to test all strings of even length which is countably infinite.

I have tried reducing $HALT^-$ to $L$ but not succeeded. Is it unrecognisable or not? How would you prove it?

Thanks.


texts:
Going with the definition, that order of a B+ tree is the maximum number of children a node can have.

What is exactly meant by the order of a leaf node? As per my understanding order of a leaf node is the number of  pairs it can hold.

But in general when order of a B+ tree is defined in a question like, order is 5. Example:https://www.tutorialcup.com/dbms/b-tree.htm . Then we assume the leaf nodes to have keys in [n/2] to n-1(3 to 4).

If we assume the leaf can contain 5 pairs, then the upper limit on keys should be 5 and not 4. Could someone explain why its taken to be n-1 in every B+ tree insertion tutorial.


texts: Correctness of an algorithm difference between recursive and iteraive

texts:
I know that the general strategy to do the correction of an algorithm is as follow :

  if the algorithm is recursive then prove the correctness using induction
  if the algorithm is iterative (using a for loop for example) then find an invariant

Finding an invariant is sometimes hard while induction is easy. So since every iterative algorithm can be transformed into a recursive one, why do we bother finding clever invariant while we could do :

  find the recursive equivalent algorithm -> use induction

Maybe the part : "transform the iterative program into a recursive one" is hard, but for simple programs it's definitely worth it. I mean sometimes it is (at least for me) very hard to find invariant, but when doing induction everything is "easy".

So I guess I am missunderstanding something ?

Thank you !


texts: Is there a random shuffle algorithm using only true /false?

texts:
Is there a way to randomly shuffle an array using only a source of random boolean values?  SO to clarify, shuffle using true /false only, and not integers or decimals.

For this question, I'm specifically excluding an approach whereby the booleans are just arranged into an integer and then it's used in a Fisher-Yates shuffle. I'd be repeatedly shuffling approximately 30,000 items and have a ready source of random booleans.  I'd need to build up a very large integer for Fischer-Yates to avoid any form of bias in the shuffle.  Can this step be avoided and true /false used directly somehow?  I have the sense that some soft of bubble sort might do it, with the comparison determined randomly, but I can't quite flesh it out.

I'd be interested in any algorithm than wasn't ridiculous i.e. with a stupid time complexity of something like 2^O(n). This question builds upon some of the concepts of Best random permutation employing only one random number but isn't identical.


texts: How to minimize the sum of edge weight in the graph while keep the all-pair shortest path greater than a constant?

texts:
For example, if we have a graph G = (V, E) and a subset of vertices $U \subset V$. We can set $w(e)$ where $e \in E$ to be a non-negative real number. We want to minimize the total edge weight, but make sure that for all $(u, v) \in U \times U$, $l(u, v) \geq c$, where $l(u, v)$ is the shortest path from u to v, and c is a given constant.

I suspect that this problem is NP hard, could someone come up with a polynomial solution to this?


texts: RE Construction: Strings of even length in alphabet {a,b,c} that contain exactly one a

texts:
i am reviewing older exams from my computational theories lesson in university and i am struggling to figure this one out:
Construct a regular expression for the following language: Strings of even length in alphabet {a,b,c} that contain exactly one a.

Roughly translated from greek, hope it makes sense. Thanks


texts: Comparing locally maximal and localy minimal Hamiltonian paths

texts:
Let $K_n$ be a weighted complete graph on $n$ vertices. Two Hamiltonian paths are
formed as follows. The first one, $H$, is formed by starting at an arbitrary vertex, and at each stage proceeding from the current location to the unvisited vertex maximizing the weight of the connecting edge. The second one, $h$, is formed similarly, except that at each stage one chooses the unvisited vertex minimizing the weight of the connecting edge. Prove that $w(H) \ge w(h)$.

I tried with induction. For $k=3$, the conclusion is fulfilled. We assume that $w(H)\ge w(h)$ for a Hamiltonian path with size $n-1$ and try to prove it for a Hamiltonian path with size $n$, where I got stuck. How can I go ahead with induction?


texts: Improvement of algorithm due to constrained graph

texts:
This algorithm runs natively in O(V * E^2).

The description states that

  The running time of O(V * E^2) is found by showing that each augmenting path can be found in O(E) time, that every time at least one of the E edges becomes saturated (an edge which has the maximum possible flow), [...]

My graph has the property that at there are exactly |V| edges with a limited capacity, that is, all remaining |E|-|V| edges have an unlimited capacity; any amount of flow can pass through them.

Given that those edges with an unlimited capacity can never become saturated, can I safely assume that a maximum of |V| augmenting paths will be found, and therefore the complexity reduced to O(V * E)?

If so, is there an adequat proof for the assumption made in the Wiki article? It only states There is an accessible proof in Introduction to Algorithms.


texts: Is it immediately true that the class of P is a subset of the class NP?

texts:
Forgive me if this is a stupid question - it's been a while since I thought at all about complexity theory and I want to make sure that I have covered all the possible angles with regards to the basics.

My question is, is it immediately true that class P is a subset of the class NP? That is, do we need to prove that the set of problems for which a solution may be obtained in polynomial time, is a subset of the class of problems for which a potential solution may be verified in polynomial time?

For example, consider a problem has multiple solutions and suppose that at least one of these solutions can be found by a program that runs in polynomial time. Then this problem is clearly in the class of P, since a solution can be found in polynomial time.

However, this does not tell us that all solutions are verifyable in polynomial time. Could it not be the case that some other solution to the problem is very difficult to verify?


texts: Confusion about the definition of de Bruijn terms in the TAPL book

texts:
I'm working through Types and Programming Languages right now, and I'm a little confused about the recursive definition given for nameless/de Bruijn terms  (chapter 6, definition 6.1.2). Below is the definition given:

  Let $\mathcal{T}$ be the smallest family of sets $\{\mathcal{T}_0,
\mathcal{T}_1, \mathcal{T}_2, \ldots \}$ such that

  $k \in \mathcal{T}_n$ whenever $0 \leq k < n$;
  if $t_1 \in \mathcal{T}_n$ and $n > 0$, then $\lambda.t_1 \in \mathcal{T}_{n-1}$;
  if $t_i \in \mathcal{T}_n$ and $t_2 \in \mathcal{T}_n$, then $(t_1 t_2) \in \mathcal{T}_n$.

It further clarifies that the elements of $\mathcal{T}_n$ are terms with at most $n$ free variables, numbered between $0$ and $n-1$.

I think I understand the first two points, but the third is confusing me. Here's my understanding of what the points mean:

The numbers $0, 1, \ldots, n-1$ are all terms in $\mathcal{T}_n$ (representing $n$ unbound variables).
$t_1$ has at most $n$ free variables, and $\lambda. t_1$ binds a single variable ($0$), so it has at most $n-1$ free variables.

Assuming these are correct, my current feeling about point 3 is that $(t_1 t_2)$ should actually be in $\mathcal{T}_{2n}$, because the resultant term will have up to $2n$ free variables ($n$ each). I don't follow how $(t_1 t_2) \in \mathcal{T}_n$.

Could somebody help correct my understanding?


texts: Problem with the pseudo random number generator One-Time-Pad

texts:
I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $XOR$ and get the cipher text. This encrypts the message and to decrypt the message you'd  do $XOR$ with the cipher and key bits.

Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator, where the original key is $n$-bits long (and doesn't have to be as long as the message). Then you'd put the key in the generator and get a pseudo random number. But since it's pseudo random, wouldn't the sender and receiver get different keys? Then how can the receiver decrypt the message if they don't have the same key?


texts: Least number of circular segments covering N points on a circle

texts:
I found this problem to be similar to the problem of Finding least number of line segments with length L that cover N points.

The problem is:

  Given N points on a circle, find the best positions of fixed size circular segments that cover all those points so that the number of circular segments is minimal.

I think that we can reduce the problem to:

  Finding the best positions of fixed size linear segments to cover all N points on a line where upon reaching the end of the line, you "jump" to the beginning of it (so a line segment that exceeds the end of the line will have its remaining length continuing at the beginning of the line).

Will the greedy approach presented on the linked question work with some adjustments or given the possible overlap of segments the problem changes fundamentally? How can this be solved optimally?


texts: Prove that $P/poly$ is closed on $^*$. Please help me with that because I cannot deal with that.


texts: no of times partion is called in quick sort, assuming array is always halved

texts:
In the most even possible split, PARTITION function produces two subarrays, each of size no more than n/2. since one is of size floor(n/2) and one of size ceil(n/2)-1.
The recurrence for the running time will be,
$$
T(n) = 2T(n/2) + \Theta(n)
$$
where we tolerate the sloppiness from ignoring the floor and ceiling and from subtracting 1. By case 2 of the master theorem, this recurrence will have the solution
$$
T(n) = \Theta(n \log n)
$$
My Implementation is as follows:
QUICKSORT(A, p, r)
  if p < r
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
  x = A[r]
  i = p - 1
  for j = p to (r - 1)
      if A[j] <= x
          i = i + 1
          exchange A[i] with A[j]
  exchange A[i+1] with A[r]
  return i + 1

Assuming that the array is always divided into 2 equal halves, how many times is the partition algorithm will be called?


texts:
The Max-Cut optimization problem on a graph $G=(V,E)$ can be written as the question of wanting to maximize the function $\frac{1}{4} \sum_{(i,j) \in E } (x_i -x_j)^2$ under the constraint $x_i^2 = 1, x_i \in \mathbb{R}, \forall i \in V$.

Now the usual SDP relaxation is to lift the $x_i$s to vectors $\vec{x_i} \in \mathbb{R}^d$ for some $d$ with the new objective function to be maximized being $\frac{1}{4} \sum_{(i,j) \in E } \vert \vert \vec{x_i} - \vec{x_j} \vert\vert _2 ^2$ under the new constraint being $\vert \vert \vec{x_i} \vert \vert _2 ^2 = 1$.

I wonder why in the usual SDP relaxation we use the $l_2$ norm. Is that just convenience or is there some optimality argument about it? Like one could have as well for any $4$ integers $p,q,r,s$ thought of,

maximizing $\sum_{(i,j) \in E } \vert \vert \vec{x_i} - \vec{x_j} \vert\vert _p ^q$ under the constraint being $\vert \vert \vec{x_i} \vert \vert _r ^s = 1$.

I believe this optimization problem would still give the max-cut?

Beyond the fact that such an optimization would probably be very hard to do, is there any fundamental reason why we do not do such a formulation of optimizing the $q^{th}$ power of the $p-norm$ under a constraint fixing the $s^{th}$-power of the $r-norm$?

(will there emerge constraints on the integers $p,q,r,s$ for this to work?)

For example,

Even before the relaxation one could have as well written the optimization question as wanting to optimize $\frac{1}{16} \sum_{(i,j) \in E } (x_i -x_j)^4$ under the constraint $x_i^2 = 1, x_i \in \mathbb{R}, \forall i \in V$. I believe this would still give the same max-cut!

And then one might have thought of its "natural" SDP relaxation to be,

maximizing $\frac{1}{16} \sum_{(i,j) \in E } \vert \vert \vec{x_i} - \vec{x_j} \vert\vert _4 ^4$ under the constraint being $\vert \vert \vec{x_i} \vert \vert _2 ^2 = 1$.

Do we know that say the above SDP won't beat the $0.878$ factor?


texts: Decide if a specific Turing machine halts on a specific string

texts:
Can you always decide if a specific Turing machine accepts a specific string?

I started thinking about this after reading an answer to this question, Rice's theorem vs Turing completeness, which seams to you can.

If this is true, intuitively, it seams it would be implied that HALT could be decided, which is obviously not true.  Otherwise what is the difference?


texts: Are these two relations on integers partial orders?

texts:
Are the following relations $R_1$ and $R_2$ defined on the set $\mathbb{Z}$ of integers partial orders? (A partial order is reflexive, antisymmetric and transitive.)

$a$ $R_1$ $b$ if and only if $a = 2b$.
$a$ $R_2$ $b$ if and only if $a^2|b$.

Would someone help me understand?


texts: Find maximum in array without comparisons between elements

texts:
Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$.

The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions:

$\cal{F}$ should not compare any $a_i$ with any $a_j$ ever.
$\cal{F}$ also should not add, subtract or exploit some fancy facts about integers
$\cal{F}$ may, however, compare any $a_i$ with some predetermined constant number, and this number may depend on $N$

Why does algorithm exist? Well, counting sort will work, it never compares elements with each other. Its complexity is $O(n+N)$.

I propose this:

compare all $a_i$ with $N/2$, let $L=\{a_i\in A|a_i<\frac{N}{2}\}$, $U=\{a_i\in A|a_i\geq\frac{N}{2}\}$.

If $U$ isn't empty, we may throw $L$ away and compare $U$ with $3N/4$, etc...

If $U$ is empty, we have our initial problem but now the upper bound is $N/2$. Call algorithm recursively.

Basically, it is binary search on $N$, so it will do in $O(n\lceil\log N\rceil)$ in the worst case. If $N$ is big enough it is better than counting sort.

Two questions:

a) am I correct with my algorithm? I can't see any flows in binary search implementation.

b) it is not obvious to me that binary search in this problem is the best solution, is it possible to do better? If not, how to prove it?

I've added some more explanation to clarify the question. According to comments (thanks, EvilJS) I've used term "comparison-based sorting" wrong, so sorry for that.


texts: Rice Theorem - What is non-trivial property?

texts:
Every nontrivial property of the recursively enumerable languages is undecidable.

What exactly is nontrivial property?


texts:
I can calculate the time complexity of the following loop:

for (int i = 1; i < n; i++)

The time complexity of it is $O(n)$.

but I can't calculate the time complexity of the next two loops.

I can't find any hints.

for (int i = 0; i < n; i+= 2)

for (int j = 1; j < n; j*= 2)


texts: Find n-th number in a number system with only 3 and 4

texts:
Given a number system with only 3 and 4. Find the nth number in the number system.

There is a solution given here but its very vague without explaining the mathematics/ concept behind it. Can someone please help me derive the logic for framing an algorithm for this question?

One approach that crosses my mind is, we can think of this number system as also a binary one ( in 3 and 4, instead of 1 and 0)
Thus, we could possibly convert the nth number to its corresponding binary format and replace 0 with 3 and 1 with 4. One problem here though is that say the nth number is 333. This in the regular (0 and 1) binary system would be 000 = 0, which evidently is wrong since the nth number is not 0.


texts: Should we assume both processes are getting same CPU clock while we solve SYNCHRONIZATION problems in uniprocessor system?

texts: In synchronization, when one process is in a critical section & another is busy waiting,  both are using CPU. But in a uni processor system, in the same clock both cant get the CPU. So there must be a scheduling algorithm for them. Should we consider these while solving synchronization problem or should we think both are doing their work on the same clock while we solve problems in synchronization?


texts: Is it possible to use dynamic programming to factor numbers

texts: Let's say I am trying to break all the numbers from 1 to N down into their prime factors. Once I have the factors from 1 to N-1, is there an algorithm to give me the factors of 1 to N using dynamic programming?


texts: What does $\cdot$ mean as a notation with complexity classes?

texts:
In the wikipedia page for Toda's Theorem, the notation $A\cdot B$ is used where $A$ and $B$ are two complexity classes, but without explanation as to its meaning.

SO given two classes $A$ and $B$ what does $\cdot$ mean in $A\cdot B$?

Using an example for the cited page, what would $BP \cdot \oplus P$ mean?

Is it correct to say $A\cdot A=A$, and when is it true that $A\cdot B=B$ or $A$?


texts: Showing $L=\{a^ib^jc^k: i,j,k \text{ not all equal}\}$ is a CFL a lemma

texts:
In their answer, Janoma proves that $\{a^ib^jc^k:i\neq j,j\neq k,i\neq k\}$ is not context-free using Ogden's lemma, but I haven't learned about Ogden's lemma yet. I wanted to know whether Ogden's lemma can be dispensed with.

This could be interpretted as $\{a^ib^jc^k: i,j,k\text{ are not all equal}\}$ correct?
Can someone show that this is context-free without a lemma?
Like making a CFG or PDA?

This is just for my own reference for learning.


texts:
I have a question. Assume $L = \{ a^m b^m \mid m ≥ 1 \}$ is not a regular language.  Prove that $I = \{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0 \}$ is not a regular language.

I can prove it with pumping lemma but the question is to solve it by using the assumption.

Thanks.


texts: An algorithm for topological sorting based on depth-first search: why do we need two tags?

texts:
Wiki gives an alternative algorithm for topological sorting is based on depth-first search, as follows:

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then return
    if n has a temporary mark then stop   (not a DAG)
    mark n with a temporary mark
    for each node m with an edge from n to m do
        visit(m)
    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

I couldn't see the necessity of introducing two tags: permanent and temporary. As far as I can see, the following algorithm would work, using only one tag -- explored.

L ← Empty list that will contain the sorted nodes
while exists nodes without an explored mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    mark n as explored
    for each node m with an edge from n to m do
        if m is unexplored
            visit(m)
        if m is explored
            stop(not a DAG)
    add n to head of L

If it's not the case, please tell me where I went wrong within this algorithm.


texts: Data structure with init $O(n)$ and interval max $O(\log n)$

texts:
I need to find a data structure that supports the following operations:

init(A): gets an array of size $n$ of different numbers and builds the data structure - should be $O(n)$.
max(i,j): gets two indexes $i<j$ and returns the maximum value between these two cells, that is, $A[i],A[i+1],\dots,A[j]$ - should be $O(\log n)$.

It should be a tree related data structure.


texts:
Suppose that I have a tree where each node is either of type A or type B.

Nodes of type A have outgoing edges only to nodes of type B and vice versa.

Is there a name/term for this kind of a tree?

A concrete example of such a tree would be the state tree of a 2 player game (like tic-tac-toe) which has alternating levels of states where it's X's turn or Y's turn.


texts:
I'm reading Garey & Johnsons "Computers and Intractability" and I'm at the part "Some techniques for solving NP-Completeness". Here's the text about Proof by Restriction:

  Proof by restriction is the simplest, and perhaps most frequently
  applicable, of our three proof types. An NP-completeness proof by
  restriction for a given problem $L \in NP$ consists simply of showing that
  $L$ contains a known NP-complete problem $L'$ as a special case. The heart
  of such a proof lies in the specification of the additional
  restrictions to be placed on the instances of $L$ so that the resulting
  restricted problem will be identical to $L'$. We do not require that the
  restricted problem and the known NP-complete problem be exact
  duplicates of one another, but rather that there be an "obvious"
  one-to-one correspondence between their instances that preserves "yes"
  and "no" answers."

And I'm trying to learn this technique by example, but need some help.

(If you have the book, my example is on page 65, 27th printing)

They prove that Multiprocessor Scheduling is NP-complete with the following proof:

(Paraphrasing):

  Restrict to PARTITION by allowing only instances in which $m = 2$ and $D$
  $=$ half the total sum of the "lengths".

Here $m$ is the number of processors and $D$ is the maximum allowed sum of "lengths" per processor.

This is obviously a special case of multiprocessor scheduling which is solvable by solving the PARTITION problem, and there's no confusion there.

But, I'm not sure why this proof holds.

Excerpt from above: "The heart of such a proof lies in the specification of additional restrictions to be placed on the instances of $L$ so that the resulting restricted problem will be identical to $L'$ ".

The way I see it that means we have to find the special case, and then find restrictions that show us that this problem can always be reduced to the special case. What we're trying to do here is show that Problem $A$ (MS) is at least as hard as Problem $B$ (PARTITION), so why would a simple special case be enough here? Is it because there's an obvious way to map to this special case that I'm missing? Or perhaps because $m = 1$ is trivial and we know that the problem will only get harder with a higher $m$, and that $D$ is always arbitrary, therefore $A$ must be at least as hard as $B$ (I feel like I'm just guessing now :p)

I hope it is clear where I get lost.

TLDR; Why is it enough to find a special case that is solvable by an NP-Complete problem? Don't we need some reduction to complete the proof?


texts: Other encodings of the natural numbers that are not the Church encoding or the Scott encoding

texts: Are there other encodings of the natural numbers in the untyped lambda calculus which are neither the Church encoding nor the Scott encoding?


texts: What happens when a file is being moved/copied to another location at the same hard drive?

texts:
I've got a few questions about how hard-drives works with information that I haven't been able to find the answers to anywhere, so I figured I'd give this a shot instead. I know the basics on how computers store/retrieve data from the disks, but I've got a few other questions that I'm not so sure about.

Firstly, What happens when you move a file from one map to another (via the file explorer)?

Does the computer look at the FAT-table to see where the data is stored, and then use the table to store the data in the new map?

Secondly, What happens when you copy a file from one map to another?

Thanks in advance.


texts: Finding maximal independent sets in an independence system

texts:
An independence system is a collection $I$ of subsets of $\Omega$ such that if $A\in I$, then any subset of $A$ is in $I$. These sets are called independent.

Suppose I have an oracle for testing independence. In particular I have an ambient set $\Omega$ and an independence system $I$ of subsets of $\Omega$. I pass a subset $A$ of $\Omega$ to the oracle, and it tells me if $A\in I$.  Is there an efficient algorithm for finding all maximal independent sets?  I especially care about minimizing the number of calls to the oracle, which is expensive.

I implemented a brute force method (just looping over the powerset) which chokes for inputs sizes above about $n=6$. On the other hand, the Bron-Kerbosch algorithm solves exactly this problem in a special case, and my implementation of it runs quite happily up to around $n=30$. That would be plenty satisfactory to me.


texts:
Are the "symbols" of a context-free grammar the same thing as the terminals?

Are the set of symbols and set of terminals the same?


texts: Suggestion for a good statistics book for computer scientists, in preparation of machine learning

texts:
We (a group of CS postdocs and Ph.D. students) are starting a shared reading of a machine learning book ("An Introduction to Statistical Learning", James, Witten, Hastie, Tibshirani).

Before diving into it, however, we felt the need to get some more solid background on simple and pure statistics. We would like to start from some statistics book, maybe from the first chapters, and then jump back into the machine learning one.

Which introductory, but sufficiently deep, statistics book can you suggest to start from?


texts: What parts of a programming language can't be defined using Regular Expressions?

texts:
I'm trying to understand how the syntax of some programming language is defined.

I know that there are some parts of the syntax of programming languages that can't be defined using regular expressions (such as an equal number of opening and closing braces) and that this is why context-free languages like BNF are needed.

What I'm struggling to understand is how one can tell which parts of the syntax of a language can only be defined using BNF and which parts could also be defined by a regular expression.

At the moment I think only BNF productions that are recursively defined can't be written as a regular expression. For example I think the following BNF can't be written as a regular expression:

<variable> ::= <letter> | <variable> <letter> | <variable> <digit>

But I think this BNF can be defined using a regular expression:

<digit> ::= 0|1|2|3|4|5|6|7|8|9

My problem with this is that I think I can write a regular expression for a recursive BNF production like this:

<word> ::= <letter> | <word> <letter>

<letter> ::= A|B|...|Z

(I'm assuming a letter is a character A-Z)

I would be greatly appreciative if someone could clarify how this works for me.


texts: Sub-linear-time ordered set (!= sorted set) implementation?

texts:
Does there exist any data structure that efficiently (linearithmic-or-similar in-order traversal, sublinear time insertion/search/removal) implements an ordered set (i.e. a set that allows for enumerating the items in insertion order)?

If so, what data structure is it/how does it do this?


texts: Are rational functions with positive integer coefficients honest?

texts:
For every rational function $p(x)/q(x)$ where $p$ and $q$ are polynomials with non-negative integer coefficients, does there exist a polynomial function $h$, such that, if you input a reduced fraction $a/b$ of length $m$ into $p(x)/q(x)$ and the output is of length $n$, then $m\leq h(n)$?

The length can be taken as the number of digits in decimal $a$ plus the number of digits in the decimal b$,$ or any other equivalent, like Kolmogorov complexity.

In other words, does there exist a rational function $p/q$ which keeps shortening fractions by more than a polynomial factor? In fact, it seems to me that it would not shorten fractions by more than a constant factor.


texts: Traversing a graph with respect to some partial order

texts:
Recently I was faced with the following Graph traversal problem:
"Given an arrangement of buildings in form of a DAG. All the buildings have to be colored, but there is an order for that represented by edges in the DAG. If there is an edge from A->B, this would mean building B can only be colored after building 'A' has been colored. Also given is an array which provides the initial cost of coloring each building (vertex) in the graph. The actual cost of coloring a building 'v' is I(v) * C(v), where 'I(v)' is the number of buildings colored before 'v' plus '1' and C(v) is its initial cost of coloring provided in the array. Find the minimum actual cost of coloring all the buildings in the graph."

If there an is an edge from A->B, building B can be colored only after building A has been colored. Of course, there can be multiple routes to B in the graph, for instance from A->B and C->B. In this case if the provided array is (2,1,3) for coloring (A, B, C), and we choose to color building in the order of (A, B, c) then total cost = 1*C(A) + 2*C(B) + 3*C(C) = 1*2 + 2*1 + 3*3 = 13. However we cannot have an ordering where B is colored first.

I came up with a brute force solution to this problem. Topological sorting might help, but I couldn't really figure out how. Any suggestions?


texts: Is it possible for a DFA to have less states than its equivalent NFA? Number of transitions does not matter. If possible also give an example.


texts: How do I go about creating a mapping reduction?

texts:
So I understand what a mapping reduction is and how to create them for simpler problems such as a reduction from the set of even numbers to set of odd numbers however, seemingly more complicated questions trip me up such as the following...

A and B are computable languages where B is non trivial give a mapping reduction from A to B.

So my thought process with this question is that the reduction must have something to do with the fact that B is non trivial, but I'm not sure.

Any help understanding mapping reductions and this question would be appreciated!


texts: Is the longest Hamiltonian cycle NP-complete?

texts:
As I understand it to prove something is NP-complete you have to show that it's NP-hard by reducing and a known NP-complete problem to your problem and also prove that it is in NP which you do showing that an answer can be verified to be correct in polynomial time.

Now for the longest Hamiltonian cycle in a weighted graph, I know how the reduction would work, but I'm confused about how to verify a solution in polynomial time. To verify that the cycle is Hamiltonian is easy but how would I know if a cycle I'm looking at really is the longest?

Any help would be appreciated!


texts: Designing DFA for accepting a string with a 1 in the tenth place from the right over an alphabet {0,1}

texts: I'm stuck trying to implement a DFA to do this. Everything I've tried so far seems to have to be able check the next nine elements to determine if the string terminates. Any tips?


texts: A O(n) algorithm for a point set triangulation

texts:
I'm currently stuck at the following task:

Consider a point set $S = \{ p_1, p_2, ..., p_n \}$ in the plane in general position (i.e., no three points of $S$ are collinear). The points of $S$ have pairwise different $y$-coordinates and are sorted in increasing order of them, i.e., $y(p_i) < y(p_j) $ if and only if $i < j$.
Develop an algorithm that computes a triangulation of $S$ and needs $O(n)$ runtime and memory.

I found out how to triangulate monotone polygons, which is pretty close to the task, but I don't know how to transfer this into a triangulation of point sets in case the monoton polygonial has a "notch".

I'd be thankful for any kind of help.


texts: supply a matching data structure that supports MakeEmpty, Insert and DeleteFreq

texts:
I've been struggling with solving the following question:

Supply an ADT that stores members (not necessarily unique) and supports the following functionalities:
1) MakeEmpty - creates an empty data structure - complexity in time Θ(1) worst case
2) Insert - inserts a member into the data structure - complexity Θ(1) in average case
3) DeleteFreq - gets out the most frequent member from the data structure (the member exists the maximal number of times in the data structure) - time complexity Θ(log(n) in worst case

At the beginning I was thinking about using a hash table (because of the average time of Insert function) and the hash-table based on keys of the members. In addition, for each cell in the hash-table I thought about holding a pointer to AVL/2-3 Search Tree.

But then, I'm thinking it's possibly not correct because only hash-table initialization (all pointers to NULL) gonna cost Θ(hash-table-size). Furthermore, Insert function could be much more expensive if the load factor isn't good.

I would appreciate your advice and guiding


texts: Does master theorem apply differently for $n$ with restrictions?

texts:
Given $T(1) = 1$ and $T(n) = 4T(n/2) +n^2$ for $n\geq 2$, can I solve the recurrence for $T$ by applying the master theorem with $a = 4$, $b = d = 2$?

This would give $T(n) = \Theta(n^2\log n)$.


texts: Proving that a language is not in P using diagonalization

texts:
Pardon me if i'm missing something which is very obvious here but i cant seem to figure it out.

$E=\{ \langle M, w \rangle \mid \text{ Turing Machine encoded by $M$ accepts input $w$ after at most $ 2^{|w|}$ steps}\}$

We have to prove $E\notin P$

The book (Papadimitrou, Elements of the ToC) assumes $E\in P$ and it constructs another language (a diagonal one)

$E_1=\{\langle M\rangle \mid \text{ Turing Machine encoded by $M$ accepts input $M$ after at most $  2^{|M|}$ steps}\}$

and takes its complement language $E_1'$ and it follows that with the assumption $E\in P$ , it is true that $E_1' \in P$

The question it then asks is the following: Say the polynomially bounded turing machine to decide $E_1'$ is $M^*$ then what happens when $M^*$ is presented with $M^*$ as an input?
Now I understand it cant give an yes because that results in a contradiction. My doubt is where is the contradiction if the answer is no?


texts: How to find rows of matrix that are zero everywhere except for 1 entry?

texts:
I am interested in finding the rows of a matrix where all entries are equal to zeros except for one.

Example: Given the following matrix:

\begin{bmatrix}0  &0 &3 & 8\\ 0 & 4 & 0 & 0 \\ 0 &1 & 0  & 1\end{bmatrix}

Only the second line has this property.

Of course, the brute force way is to go over the entries and check them one by one. But I am wondering if there is another most efficient way I don't know about.


texts: Is rejecting in polynomial time required for language to be in P?

texts:
Language $L$ is in $\mathrm{P}$ if and only if there exists some Turing Machine $M$ such that for every word in $L$, $M$ either accepts or rejects it in polynomial time. Right?

But what if all we know about our language is that there exists TM $M'$ such that for every word in $L$, $M$ accepts it in polynomial time, but for words not in $L$ it might not halt at all, for example? Is existence of $M'$ enough to say that $L$ is in $\mathrm{P}$, and why/why not?


texts: When does an algorithm run in $O(1)$ time?

texts:
When can an algorithm be said to have $O(1)$ complexity? My doubt is if $n$ is specified to be a large number but constant and we cannot implement it in reality without a loop even then can we call it to have $O(1)$ time complexity? Consider the following examples.

Algorithm to add first 1000 natural numbers (that is I mean to say if n is specified directly). Then can we say this has $O(1)$ time complexity?
Finding the $7$th smallest element in a min heap. This element is present in anywhere in the first 6 levels of the heap (considering root at level 0). So to find the element we need to check $2^7 - 1$ elements. Then can we say this has $O(1)$ time complexity?


texts:
Is the following statement always true:

  if there is a mixed-strategy Nash equilibria then it is unique.

I know that there can be several pure strategy Nash equilibrias.


texts:
Let CVal be the language of all $<C,s>$ where $s$ is an $n-$tuple of binary values ($\{0,1\}$), such that $C$ is a variable-free boolean circuit (gates $\wedge$, $\vee$, $\neg$, $0$, $1$), and it outputs $1$ for the entries of $s=(x_1,...,x_n)$.

Given two languages $A,B$, define $A \leq ^{rand} B$ iff there exists a random turing machine $M_f$ with $O(\log n)$ memory, such that for each $x$:

if $x\notin A$ so $f(x)\notin B$
else, if $x\in A$, then $P(f(x) \in B) \geq \frac{1}{2}$.

I'd like to show that for each $A\in RP$ exists such a random reduction: $A\leq^{rand} CVal$.

My thoughts were to prove this  similarly to how it can be proven that for any $A\in P$ exists a log-space reduction $A\leq_l CVal$ . Meaning, I'd like to show that for every $n$ I can construct $C_n$ such that in probability $\geq \frac{1}{2}$ $\,:\,\,$ $C_n(x)=1$  for every $x$ in length $n$ which is in $A$, and for each $x$ not in $A$ $C_n(x)=0$ for sure, but I'm not sure if perhaps there is an easier way for showing a random reduction $A\leq_{rand} CVal$ for each $A\in RP$?

Thanks!


texts: Trying to understand the iterative method for solving recurrences in this example

texts:
This question: Solving the recurrence T(n) = 3T(n-2) with iterative method has a pretty straightforward step-by-step for solving this particular recurrence.  But, I'm having trouble understanding two things.

1) How dos OP arrive at this general form?  If we know T(n)=3T(n−2) and T(n−2)=3T(n−4), then my substitution gives:

T(n)=3T*3T(n−4)

Why is it not 3T*3T, or 3T^2?  Is it some specific behavior of T that determines this?

T(n)=3∗3T(n−4)

leading to the general form:

T(n)=3kT(n−2k)

2) where does the above k variable come from, exactly?  I understand that you'd combine the 3s to have 3^2, but how do you replace 3^2 with 3^k?

Thanks in advance!


texts: Marginal Probability of Generating a Tree

texts:
Fix some finite graph $G = (V, E)$, and some vertex $x$.

Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows:

Let $T_0 = \{ x \}$.
For $0 < n \leqslant N$

i. Let $B_n$ be the set of neighbors of $T_{n-1}$ outside of $T_{n-1}$.

ii. Form $T_n$ by

Sample a pair $(x_n, y_n) \in E(G) \cap \left( V (T_{n-1}) \times B_n \right)$, with probability $q_n (x_n, y_n | T_{n-1} )$,
Add $y_n$ to $V(T_{n-1})$, and add $(x_n, y_n)$ to $E (T_{n-1})$.

Return $T_N$.

Suppose also that $q_n ( x_n, y_n | T_{n-1} )$ can be computed easily for all $(T_{n-1}, x_n, y_n)$. I am interested in efficiently and exactly calculating the marginal probability of generating the tree $T_N$, given that I began growing it at $T_0 = \{ x \}$, i.e.

$$P(T_N | T_0 = \{ x \}) = \sum_{x_{1:N}, y_{1:N}} \prod_{n = 1}^N q_n (x_n, y_n | T_{n-1} ).$$

My question is essentially whether I should expect to be able to find an efficient (i.e. polynomial-time) algorithm for this, and if so, what it might be.

Some thoughts:

Naively, the sum has exponentially-many terms, which precludes trying to evaluate the sum directly.
On the other hand, this problem is also highly-structured (trees, recursion, etc.), which might suggest that some sort of dynamic programming approach would be feasible. I'm not sure of exactly how to approach this.
Relatedly, I know how to calculate unbiased, non-negative estimators of $P(T_N | T_0 = \{ x \})$, which have reasonable variance properties, by using techniques from Sequential Monte Carlo / particle filtering. This suggests that the problem is at least possible to approximate well in a reasonable amount of time.


texts: Two dimensional recursive function in $O(\log n)$ time complexity

texts:
It is well known that a recursive sequence or $1$-d sequence can be calculated in $O( \log n)$ time given that it has the form
$$a_n=\sum_{k=1}^{n} C_ka_{n-k},$$
where $C_k$ is a constant. Examples would include polynomials like $n^2$ or $n^3$, exponentials like $2^n$, and Fibonacci Numbers defined by $a_n=a_{n-1}+a_{n-2}, a_0=0, a_1=1$. Factorials would not be included for example, because they are defined by $a_n=na_{n-1}$, and $C_k=n$ is not constant.
Let $a_{n,k}$ be a two dimensional sequence defined by
$$a_{n,k} = \sum_{i=0,j=0, (i\ne n \text{ }∧\text{ }j\ne k)}^{n,k}C_{i,j}a_{i,j}$$
where $C_{i,j}$ is constant.
Is it possible to compute $a_{n,k}$ in logarithmic time (a.k.a $O (\log n)$) or better?
I know one case where this is possible, namely if $a_{n,k}$ are coefficients of polynomials in a sequence ($1$-d recursive sequence), such that the degrees of each term differ by $1$. In this case, the diagonals of the sequence $a_{n,n+t}$ for some constant $t$, are $1$-d constant recursive functions, whose terms can be computed in $O(\log n)$ time. This doesn't use the initial relation in terms of two indices though as expected.
However, in certain cases, the diagonals do not form $1$-d constant recursive functions, namely when the degree difference of consecutive polynomial terms is more than $1$.


texts: Is there any research to indicate programmers are/are not moving to a hybrid of functional and object-oriented?

texts:
I am converting the OCaml Format module which does I/O and maintains state in a record with mutable values. As such it is a good candidate for me to convert to pure F#, pure C# and a hybrid.

Since this is a toss-up for me on the three versions, I am interested to know of any research papers that indicate that programmers may be moving to hybrid code of object-oriented and functional, calling one from the other, or staying with-in one programming family.

Note: I am asking for research papers not subjective answers.


texts: Matching two sets when you cannot do within-set comparisons

texts:
Suppose you have two lists, A and B, each with length n.  The elements of A cannot be compared with other elements of A--there is no order relation among them--and likewise for B.  However, elements of A can be compared with elements of B.  So for instance, suppose we have a function compareTo(a,b) where a is an element of A and b is an element of B.  If a is less than b it returns -1, if they're equivalent it returns 0, and if a is greater it returns 1.

Further suppose that a perfect matching exists between the elements of A and B, in the sense that for every element of A there is precisely one element of B such that compareTo(a,b) evaluates to 0.  And vice versa (for each b there is precisely one a such that they're equivalent).

How do we write an efficient algorithm to find the perfect matching?

My attempts: Well, there's the naive algorithm which takes an element of A and finds its corresponding element of B, repeating until all matchings have been found.  This runs in O(n^2) so we want to beat this.

It sounds kind of like Gale-Shapley but an input to that algorithm is a preference list.  In this setting we have ties, where preference lists don't.  And even generating something like a preference list would take n^2 time.  Since it is fundamental to Gale-Shapley that members of one set propose to their highest preferences of the other, this doesn't seem applicable to the given problem.

We could try to use an element of A to partition the set B and try to divide-and-conquer.  But you would only have divided B and wouldn't know which elements of A to give to the recursive call.  You could then try to use B to partition A.  To describe this more, let's give a specific example.  Suppose A = [a1,a2,a3,a4] and B = [b4,b1,b3,b2] and suppose that ai < bj if i < j, and likewise for = and >.  We could arbitrarily select a1 and then use it to partition B into the elements that come out greater in the comparison, [b4,b3,b2] and the elements that come out smaller [].  Since along the we way we found that a1 matched b1 we make that assignment and eliminate them from the rest of the algorithm.  Now that we know a1 was quivalent to b1 we can use b1 to partition A into [] and [a2,a3,a4].  We recursively call the algorithm on the smaller sets [], [] which satisfies the conditions: they have the same length and have perfect matching.  And recursively call the algorithm on the larger sets [a2,a3,a4], [b4,b3,b2] which also have the same length and have a perfect matching.

I think this algorithm is correct, but in the worst case it doesn't beat the worst-case runtime of the naive algorithm.  So I don't think I'm on the right track here.


texts: Turing machine to compute $⌈\log_2n⌉$ with 1 tape and unary input/output

texts:
I'm trying to figure out how to make the action table for a Turing Machine computing $⌈\log_{2}(n)⌉$. The input and output shall be unary (meaning $3$ should represent $111$). I can only deal with 1 tape.
Also, I would prefer having 7 transition states, 1 final state, 24 actions and 5 symbols, but any other numbers are fine too. At the end of the computation, the TM head should be at the 1st $1$ from the left, of the output.
For $⌈\log_{2}(0)⌉$, I would like to have the symbol $N$ on the tape.
I would also like an easy-to-understand explanation, if possible.


texts: grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)

texts:
Consider two sets: the set of validities of propositional logic and the set of validities of monadic predicate logic. Call the first set $VP$ and the second set $VQM$. Both of these sets are decidable, so there are Turing machines that recognize both them and their complements.

I'm interested in how the decidability of these two sets translates into grammars for them, along the lines of the Chomsky hierarchy. I have three questions:

(1) Are there context-sensitive grammars that generate $VP$ and $VQM$? The answer would be yes if the Turing machines that recognized these sets were linearly bounded, but I don't think they are.

(2) If these languages aren't context-sensitive, can anything be said about a grammar that generates them?

I would have a better grasp of the second question if I understood something about grammars between the top two levels of the Chomsky hierarchy, context-sensitive and unrestricted.

(3) There is a natural class of automata between linear-bounded Turing machines and unrestricted Turing machines: polynomially bounded TMs, exponentially bounded TMs, etc. Do these classes of TM track anything on the grammar side of the Chomsky hierarchy? If not, is there any structure to the gap between context-sensitive grammars and full-on unrestricted grammars?

(Just to be clear: I'm not talking about a grammar for propositional logic, but a grammar for its validities.)

EDIT: I thought I'd add a comment about why I'm interested in these questions. I know there is an unrestricted grammar that generates the (recursively enumerable but not recursive) set of validities of (full-on, polyadic) predicate logic. But since $VP$ and $VQM$ are not just recursively enumerable but recursive, I was wondering if the grammars that generate them might have more structure, in the Chomsky-hierarchy sense, than the grammar that generates the validities of all of predicate logic. In other words, I'm wondering if there is a grammatical way of detecting the difference between sets of validities that are recursive (as in the case of propositional and monadic predicate logic) and sets of validities that are merely recursively enumerable. What can be said about grammars of recursive but not recursively enumerable languages? Most references on the Chomsky hierarchy say nothing about this gap, but I don't know if that means there's nothing to be said.


texts: Is important for `Fisher–Yates shuffle` algorithm to generate random numbers in the sequential increment

texts:
This is a follow-up question to the Why shuffling by picking random position in all array instead of a part is not correct. I understand if I pick random numbers from all the range for 4 numbers every time the distribution won't be uniform. That's why improved Fisher–Yates shuffle algorithm picks numbers from the smaller range:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

For 4 numbers it produces the the following ranges:

[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]

My question is whether it's important that the range starts from the 0 and increments sequentially? Are the following ranges generate uniform distribution as well?

[2]           --- start from the middle
[1, 2]        --- add one number to the left
[1, 2, 3]     --- add one number to the right
[0, 1, 2, 3]

Thanks


texts: What does Cellular Automata Pre-image problem actually means?

texts:
I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata.

In the 2nd page he lists three NP-Complete problems related to CA, the first  problem is:

  CA preimage : Given a subconfiguration of length $K$, is there a configuration that could have led to it in $K$ time steps ?

I am confused with the term "Sub-configuration" and its meaning, in the paper he states that a Sub-configuration is contagious states in a finite array.

1- Does it mean a structure like Rule 110 or 90 - ECA at length $K$ ?

2- Or does it mean a pattern generated after $K$ time step in a specific structure (i.e a pattern in rule 110) ?

3- Why the problem states that the subconfiguration's length should equal to the time steps it was generated in ?  what if the problem was solvable in $K$ time steps but with a constant time steps $Z$ ?


texts: Proof of every regular language has a LL(1) grammar

texts:
I tried some examples and found that LL(1) grammar always exist.

I tried searching for formal proof but didn't find any.

Can someone give a formal proof for the above statement?


texts:
First question in the computer science section. I am currently working on a solution that optimizes decision tree redundancy.

the following is an example of optimization:

|  D1   |   D2   | Outcome |
| true  |  false |   Yes   |
| false |  false |   No    |
| true  |  true  |   Yes   |
| false |  true  |   No    |

when optimized gives:

|  D1   |   D2   | Outcome |
| true  |   -    |   Yes   |
| false |   -    |   No    |

I need to program this optimization. My decision tree will be different from the one that is shown here. I will have a string outcome, that is in no way a function of the input, and my input will contain 5 different possible inputs. boolean, string, int, double and datetime data types will also be present. Data in the input fields will be expressed using FEEL format.

What I want to know is if there already is a known algorithm for optimizing decision tables like these, or should can I expect to work this out by myself. I don't want to reinvent the wheel here, since this is quite a challenging project. An answer from the stackexchange forum suggested that I post here. He suggested that I start with the Quine–McCluskey algorithm. I looked into this, but it seems like that it's calibrated for boolen based decision tables.

Currently I am considering an approach like the flowing:

If there are no duplicate outcomes, stop process
Select rules with duplicate outcomes
See which decisions are redundant by grouping/merging them
etc

I am to write the code in C#

EDIT:
Most inputs will be comparable to a degree. For instance, a string input will be one from a set of strings, and number values will fall in a certain range. But there is no guarantee they always will be.


texts: in refutation (resolution) can we use a clause that have been resolved

texts:
In resolution if we have a set S composed of three clause C1, C2 and C3 and we want to proof that C4 is derivable from S using refutation:

suppose we've resolved C1 and C2 to C5, can we resolve C1 with C5 or C3 or C4 or C2 cause even it has been resolved?

and if we want to conceive an algorithm for that do we have to delete each resolved couple of clauses from or initial set I= {S, ¬C4} and add the resolvent instead?

and lastly, do we have to use all the clause to derive ⊥ or we stop once we find ⊥ even if we find it in the first step?

thank you for claryfing things.


texts: how to compute functional dependencies and MVDs after decomposition?

texts:
Let's say we have a relation $R$ with a set of functional and multivalued dependencies $F$, and we found a dependency that violates some normal form. Then we decompose $R$ into $R_1$ and $R_2$. How to compute the corresponding sets of dependencies $D_1$ and $D_2$?

I'm not sure if we can just take all dependencies (probably inferred by Armstrong's axioms) from $D$ which work only on attributes in a corresponding new relation, because we can lose one of the original FDs or MVDs.

Like in the famous example, $R(A, B, C)$ with $\{AB \rightarrow C, C \rightarrow B\}$ and candidate keys $AC, AB$.
The $C \rightarrow B$ violates the BCNF, since $C$ is not a superkey.
 We can't just decompose it into $R_1(C, B)$ and $R_2(C, A)$, because we then lose the $AB \rightarrow C$.

So the question is how to make sure the decomposition doesn't break our original set of dependencies and how to infer new ones for new relations?

UPDATE: I have found this is called dependency preserving decomposition. There are some algorithms I'm looking for, but I can't find them with proofs so I can understand how they work. Are there any?


texts: Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves

texts:
This problem is about finding a route on a square grid.
The starting point is $(1,1)$ and the target point $(n,m)$.
I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$.
Now I need to determine if there is a path from $(1,1)$ to $(n,m)$, and if so to return the shortest one.

Now I believe that if I trace back my steps from the input point $(n,m)$ I can always know which move I made out of the two possible ones since if $n=m$ then there is no route, this means I'm always take the smaller coordinate and subtract it from the bigger one.
But that means I have at most only one possible route to $(n,m)$ so why was  I asked to return the shortest one?

Am I missing anything ?


texts: determine if a machine prints a certain string in less time than it takes to run the machine itself?

texts:
Does there exist a procedure that determines if a polytime machine prints a certain string, and does so in less time than the machine itself takes to run?

Define a machine $a$ that analyzes another machine $b$, input $i$, and string $r$:

$a(b,i,r) = b(i) \text{ prints } r$           $[T_b = O(n^k), k >= 2]$

Is there an $a$ with run-time $T_a \in o(T_b)$ on all $b,i,r$?


texts: Why arrival process of packets at a switch is not a Poisson Process?

texts:
"Packet arrivals are not Poisson
.... but some events are, such as web requests and new flow arrivals"
I know since the network traffic is very bursty, they are not Poisson.
But I am unable to understand what "new flow arrivals" mean here and
how web requests and new flow arrivals can be considered as Poisson processes.


texts:
Is there any literature / research on the average size efficiency of stacks vs queues?  I asked because I was recently working on a problem where, if using a queue, the size quickly blew up and the computer ran out of memory.  If I used a stack the size stayed very small.

I think the reason in this case was that the search space was wide but shallow, which depth-first or LIFO optimal.  I imagine that if it were narrow but deep a queue would have worked better.

Update: The algorithm was basically counting the number of palindromes which are substrings of a given string.  My algorithm worked from the outside, pairing off letters and then sending the rest of the string back onto a stack/queue to be paired again.

Say there are 50 letters in the string, and 3 are already processed.  The number of possible substrings with 47 digits is 2^47, so if I push these all to the queue before processing the next digit it blows up.  But the stack would not push all 2^47 before processing the next string with 46 unprocessed, etc.

It comes back to what I said before about the size of the search space being much wider than it is deep - in this case the width is 2^50 and the depth is 50.  So the stack is much more efficient.  I just was wondering if there are any proven results related to this.

Update 2: At long last, here is the example I am referring to.  Consider the following procedure to count the number of palindromes meeting a certain criteria:

int c = 0;
var PalStruct = new Struct<string>();
PalStruct.Add("00000");  // number of zeros tells how long palindromes to count are

while (!PalStruct.isEmpty()) {
  var nextString = PalStruct.Remove(); // ie Pop() if stack
  var nextPos = nextZero(nextString);  // returns next zero index from left, -1 if none
  if (nextPos==-1) {
    if MeetsCriteria(nextString) c++;
  }
  else {
    foreach  (char x in alphabet) {
      var sb = new StringBuilder(nextString);
      sb[nextPos] = x;
      sb[nextString.Length-1-nextPos] = x;
      PalStruct.Add(sb.ToString()); // ie Push() if stack
    }
  }
}

// c is result

So here is the thing: if Struct is a stack, then the maximum size of the structure will be O(L), where L is the length of the palindrome.  If Struct is queue, however, the maximum size of the structure will be O(a^L), where a is the size of the alphabet.


texts: Ordering vertices of graph based on specific vertex-transitivity

texts:
Given any complete directed weighted graph $G$ with $n$ vertices and matrix of non-unique weights $W$, find a weak ordering $T(G, W)$ on the vertices of the graph satisfying the following conditions:

$T(G, W)$ is invariant under permuting the vertices
For any two vertices $u$ and $v$, $u = v$ in $T$ if and only if there is some automorphism $f:V(G) \rightarrow V(G)\ $ such that $f(u) = v$ and $f(v) = u$

The reason I want such a thing is to have some consistent but arbitrary way to order the vertices of a graph that is invariant under permutation, as a tie-breaker for more meaningful orderings, when the vertices are actually distinct, which will usually be the case. If two vertices cannot be distinguished, picking whichever one happens to be first in my representation is fine.

I expect this problem is in $NP$, as it seems like there's some way to compute graph isomorphisms with it, but my graphs are small and I can precompute the ordering once, so it would still be useful to figure out how to do it.


texts:
I have been posed a question by my lecturer and I'm trying to figure the right way to go about it. They want me to ensure mutual exclusion for n processes. The code provided is as follows:

Process Pi
    while(true){
            while(#taken == 5){}

            #taken := #taken+1;
            // enjoy a non-alcoholic drink //

            #taken := #taken-1;
        }
    }

The task provided is Add synchronization code such that the requirements for the bar
are enforced. i.e. only five people at the bar at a time. Assuming n processes how can I make sure that only one process can enter the critical section at a time? I've tried this:

s = 1
Process Pi
    while(true){
        if(s > 0){
            while(#taken == 5){}

            #taken := #taken+1;
            // enjoy a non-alcoholic drink //

            #taken := #taken-1;
            s=s-1
            }
        }
    }

But it doesn't appear to me mutually exclusive. They also said this in a study group this evening:

You may also assume the existence of mutual exclusion variables that support the operations preprotocol(mutex) and postprotocol(mutex) to create critical sections.

I don't really understand what this means. Would anyone be able to shed any light on this issue?


texts: CFG for language of all palindromes whose number of 1s is divisible by 3

texts:
The question is the following:

  Construct a CFG for $L_2 = \{w \in \{0, 1\}^* \mid w = w^R\text{ and the number of 1’s in $w$ is divisible by 3}\}$.

I can construct a CFG for $\{w \in \{0,1\}^* \mid w = w^R\}$ as follows

$$S → 1S1\mid 0S0\mid 0\mid 1\mid \epsilon$$

I don't understand how to make $w$ divisible by 3 in my CFG.


texts: Time complexity for the 'Restore IP Addresses' problem

texts:
There's a programming problem 'Restore IP Addresses' where given a string containing only digits, restore it by returning all possible valid IP address combinations. Example, "25525511135" returns ["255.255.11.135", "255.255.111.35"].

My solution basically breaks up the string (upto 3 chars at a time) and moves to the remaining part of the string. This way we build a list of valid ip addresses using recursion. I've pasted my solution below.

If the input is number of characters (n) what would the time complexity of this solution be (with an explanation)? Also, would memoization help in this case?

/**
 * @param {string} s
 * @return {string[]}
 */

function isValid(s) {
  if (s.length === 0) return false;
  if (s.length > 1 && s[0] === '0') return false;
  if (s > 255) return false;
  return true;
}

function breakString(s, parts) {
  if (parts === 1 && !isValid(s)) return [];
  else if (parts === 1) return [s];

  let ret = [];

  //break into 3 pieces
  for (let i = 1 ; i <= 3 ; i++ ) {
    let part1 = s.slice(0, i);
    let part2 = s.slice(i);
    if (!isValid(part1)) continue;
    let tmp = breakString(part2, parts-1);
    if (tmp.length === 0 ) continue;
    tmp = tmp.map((str) => part1 + "." + str);
    ret = ret.concat(tmp);
  }

  return ret;

}

var restoreIpAddresses = function(s) {
    return breakString(s, 4);
};