texts: Vertex pertubation along an edge and a triangle

texts:
I am trying to implement a mesh generation algorithm. Input to the algorithm is a set of constraints(imposed on output mesh) called Piecewise Linear Complex(PLC) which is a collection of vertices $V\subset\mathbb R^3$, edges $E=\{(a,b)|a,b \in V\}$ and triangles $T=\{(\alpha,\beta,\gamma)|\alpha,\beta,\gamma \in V\}$.

In one of the stages of the algorithm I need to perturb a vertex $v$ along an edge $e$, similarly I also need to perturb a vertex along the plane of a triangle $t$. Perturbation should be the smallest non-zero disturbance which will preserve Delaunay edge property for all edges in $E$.

My assumed definition of a Delaunay edge is: An edge is Delaunay, iff there exists a circumsphere of its endpoints not containing any other vertex inside it.

So I have two problems:

Perturbation along an edge:

In this case, I think that I need to shift the vertex by a small step along both directions on the edge and test in which case Delaunay property of all edges is preserved. But how should I decide the step size?

Perturbation along a triangle:

Extending my basic approach to 2 dimensions, my step will be a 2D tuple now and again I don't know how to decide its value?

Since perturbation should be the smallest possible disturbance, it seems to me that step size will be different for different machine representations.

So, my questions are:

Is there any other more efficient(requiring lesser number of operations) approach for this vertex perturbation problem?
If not, can we decide step size which can work reliably regardless of machine representation?

P.S.: Reference paper for this problem is here.(Section 6: Removing local degeneracies)


texts: Time complexity of expanding decimal to new base

texts:
There is already a post on this topic on stackoverflow.

Nevertheless, I am asking the question here again, primarily because I do not understand the answer given there, and also because I have some takes on the problem I would like to supplement with.

To reiterate, we have a problem in CLRS which goes like this:

  Show how to sort $n$ integers in the range $0$ to $n^3-1$ in $O(n)$ time.

There seems to be a consensus that we first convert the numbers into base $n$, which ensures that each number is made up of at most 3 digits. Then we can use radix sort to sort the number in $\Theta(3(n+n)) = \Theta(n)$ (the parameter $k$ equals $n$ because we are in base $n$).

What I am concerned with is the cost of converting the $n$ numbers to and from base $n$. Converting back to decimals is $\Theta(1)$ obviously, so $n$ conversions equals $\Theta(n)$. But converting a decimal to another base takes $\Theta(\log n)$, so that the first $n$ conversions to base $n$ would take $\Theta(n\log n)$ time, and break the time complexity of $\Theta(n)$ of the algorithm overall.

I have read that you can view the expansion as a $O(1)$ operation under the RAM model though I do not understand why (probably because I do not understand the difference between the RAM and BIT models in connection to complexities). In the original post the answer given also tries to explain how if integer arithmetic is done in $O(1)$ time, then "... converting a number to base $n$ is basically most significant digit: x/n, least significant digit: x%n," which I really don't get any of.


texts: Basic action for every data structure O(1)

texts:
My lecturer for Algorithms said that most of the data structures I will encounter in the algorithms course I am taking have a basic action which is of O(1).

Ex: Binary heap.

Basic action is:

  Compare 2 childen.
  Compare the "winner" with his parent.
  Replace when needed.
  Do 1-3 with the "winner", until and including the root.

How is O(1) even possible?


texts: Maximum chromatic number of sparse graphs

texts:
It is well-known that the chromatic number of a graph can be as high as $n$.

But what is the maximum chromatic number of a graph with $m = O(n)$?


texts: Does a turing machine halt with input left on tape?

texts: is the string aabb in the language of this Turing machine ?? as upon reading aa it goes to the final state but upon b there is no transition defined so won't it result in a dead configuration?


texts: Proving that NPSPACE $\subseteq$ EXPTIME

texts:
I am following "Introduction to the theory of computation" by Sipser.

My question is about relationship of different classes which is present in Chapter 8.2. The Class PSPACE.

$P \subseteq NP \subseteq PSPACE = NPSPACE \subseteq EXPTIME$

I am trying to understand why the the following part is true $NPSPACE \subseteq EXPTIME$.

The explanation from the textbook is following:

"For $f(x)\geq n$, a TM that  uses $f(x)$ space can have at most $f(n)2^{O(f(n))}$ different configurations, by a simple generalization of the proof of the Lemma 5.8 on page 194. A TM computation that halts may not repeat a configuration. Therefore a TM that uses space $f(n)$ must run in time $f(n)2^{O(f(n))}$, so $NPSPACE \subseteq EXPTIME$"

I am trying to understand why it's true, why TM that uses $f(n)$ space must run in time $f(n)2^{O(f(n))}$. Let's try to reverseengeneer the formula: $n$ is the length of the input, 2 is the size of alphabet, $f(n)$ is the space that TM use on the second tape (operational tape) and $f(n) \geq n$, but how to explain what $O(f(n))$ means. Apparently, $2^{O(f(n))}$ expreses a configuration, so $O(f(n))$ must express union of transition function and alphabet, but actually it seems like I get it wrong. The most intriguing question why, in the end,  $f(n)2^{O(f(n))}$ expressed in the terms of time, the transition from space to time is very vague for me.

I will very appreciate if someone could explain me this relationship.


texts: Can the following conditions hold all together?

texts:
Let $L_1, L_2$ be languages.

Can the following conditions hold:

$L_1,L_2\notin RE$.
$L_1\cap L_2\in R$
$L_1\cup L_2\in R$
$\overline{L}_1, \overline{L}_2 \in RE / R$

I believe the above cannot hold at the same time. I thought since $L_1\cap L_2\in R$ and $L_1\cup L_2\in R$ then $\overline{L}_1\cup \overline{L}_2\in R$ and $\overline{L}_1\cap \overline{L}_2\in R$. Then I know that $L_2 \ L_1 = L_2 \cap \overline{L_1}$. And now I want to somehow use condition 4 to reach a contradiction, but I don't see how...

Or perhaps I'm wrong and they can hold together?


texts: What is the expected time complexity of checking equality of two arbitrary strings?

texts:
The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters.
So far so good. I think we can all agree that checking equality of two equal length strings requires O(n) runtime.
However many (most?) languages (I'm using Python 3.7) store the lengths of strings to allow for constant time lookups. So in the case of two unequal length strings, you can simply verify len(string_1) != len(string_2) in constant time. You can verify that Python 3 does indeed make this optimization.
Now, if we're checking the equality of two truly arbitrary strings (of arbitrary length) then it is much more likely (infinitely, I believe) that the strings will be of unequal length than of equal length. Which (statistically) ensures we can nearly always compare them in constant time.
So we can compare two arbitrary strings at O(1) average, with a very rare worst-case of O(n). Should we consider strings comparisons then to be O(1) in the same way we consider hash table lookups to be O(1)?


texts:
I am reading Algorithms by Dasgupta et al and the graph section provides an example graph and mentions that there are 4 orderings with one of them being B, A, D, C, E, F.

Are the other 3?

B, A, D, C, F, E
B, D, A, C, E, F
B, D, A, C, F, E


texts:
I thought this question is better served in the CS part of Stack Exchange. Now that we have GPGPUs with languages like CUDA and OpenCL, do the multimedia SIMD extensions (SSE/AVX/NEON) still serve a purpose?

I read an article recently about how SSE instructions could be used to accelerate sorting networks. I thought this was pretty neat but when I told my comp arch professor he laughed and said that running similar code on a GPU would destroy the SIMD version. I don't doubt this because SSE is very simple and GPUs are large highly-complex accelerators with a lot more parallelism, but it got me thinking, are there many scenarios where the multimedia SIMD extensions are more useful than using a GPU?

If GPGPUs make SIMD redundant, why would Intel be increasing their SIMD support? SSE was 128 bits, now it's 256 bits with AVX and next year it will be 512 bits. If GPGPUs are better processing code with data parallelism why is Intel pushing these SIMD extensions? They might be able to put the equivalent resources (research and area) into a larger cache and branch predictor thus improving serial performance.

Why use SIMD instead of GPGPUs?


texts: Proof of proposition between Precise Turing Machine and Proper Complexity function

texts:
In "Computational Complexity" textbook by C. H. Papadimitriou, p. 141, he proved the following claim.

  Proposition 7.1: Let there be a DTM/NDTM M that decides a language L within time/space $f(n)$, where $f$ is a proper function. Then there is a precise TM $M'$ that decides L in time/space $O(f(n))$.

Proof. We start simulating $M'$ on input $x$ by $M_f$ ($M_f$ is same as M, it is TM with proper function $f$ on input $x$). After $M_f$'s computation has halted, $M$ uses the output string of $M_f$ as a "yardstick" of length $f(|x|)$, to guide its further computation. Now, we have two cases depending on the resources: $f(n)$ is time bound or space bound.

For if $f(n)$ is time bound, then $M'$ simulates $M$ on a different set of strings ($x_1, x_2, ...$ where for such i, $x_i$ is an arbitrary string), using the yardstick as an "alarm clock". i.e., it moves its cursor forward on the yardstick after the simulation of each step of M, and halts iff a true blank is encountered in $O(f(n))$ steps. For if $f(n)$ is space bound, then $M'$ simulates M on the quasiblanks of $M_f$'s output string. In either case, the machine is precise.

If M is NDTM, then precisely the same amount of time/space is used over all possible computations of $M'$ (the simulation of $M_f$). In both cases, the time/space is the time/space consumed by $M_f$ plus that consumed by M, and it therefore $O(f(n))$.

What is "yardstick" or 'alarm clock'? Are they the same? It is not clear what is it. Is it indicator to such i, where i is cell in tape in the Turing machine. It seems for me 'alarm clock' looks like a step in $M_f$ of simulation with $M$. So, every step is counted and stop when we simulate $M_f$ by $M$ in $O(f(|x|))$ steps.

It is not clear why do we need exactly to define $M_f$? I mean, we could simulate $M'$ by M directly without $M_f$, don't agree.

NOTE: for definition of precise TM and proper complexity function, please refer to the book pp. 140-141, or look at some slides [4-6] [here 1].


texts: How can I determine if an algoritm can be expressed as a boolean circuit?

texts: Suppose I want to express Data Encryption Standard(DES) encryption algorithm as a boolean circuit. How can I determine if what I want is practical, and if it is how can I do it?


texts: How to solve this big O notation of a fraction

texts:
I want to estimate with big O the following expressions:

$$
\begin{align*}
f_1(x) &= \frac{x^4 + x^2 + 1}{x^4 + 1}, \\
f_2(x) &= \frac{x^3 + 5 \log x}{x^4 + 1}.
\end{align*}
$$

How do you eliminate the constant on the bottom of the fraction? How would you work to solve these types of problems?


texts: A term for two algorithms which give same results but differ in complexity

texts:
Is there a technical term for a pair $(u,v)$ of algorithms, such that $u$ and $v$ have an identical output for each input (I include the option if not halting as a possible output), but they have different complexity (either time or space) as a function of their input?

An example of such a pair is (bubble sort, quicksort)


texts: Is the chalk really needed in the "chalk and string labyrinth" analogy for depth-first search?

texts:
I came across the chalk-and-string labyrinth analogy for depth-first search in Algorithms by Dasgupta et al.  I have seen the code for the depth first search.

Everybody knows that all you need to explore a labyrinth is a ball of string and a piece of chalk. The chalk prevents looping, by marking the junctions you have already visited. The string always takes you back to the starting place, enabling you to return to passages that you previously saw but did not yet investigate.

How a computer does it in code makes sense, but as a human, I think that the string is sufficient. why would I need the chalk, wouldn't see the string indicate that I have already passed a junction?


texts:
I was reading this article on the complexity class $PP$.

In the fourth paragraph there is a claim that $P^{\text{#}P} = P^{PP}$ and that it can be proved using binary search. Can anyone please explain this in better detail?
The author himself gives the following explanation: If $f$ is a $\text{#P}$ function then the language $L= {(x,k) | f(x) \geq k}$ is in $PP$. Then do binary search on $k$.

This is still not clear to me. The other direction, $P^{PP} \subseteq P^{\text{#}P}$ is clear.


texts: Why do so many 8-Puzzle solving algorithms use DFS instead of BFS?

texts:
I see so many 8 Puzzle Solvers use a stack instead of a queue. Why is that? If you are looking for the solution with the fewest number of moves, wouldn't the solution be at a shallower point in the tree, meaning that BFS would find it much quicker? Is there some subtlety to the problem that I'm forgetting that makes DFS a better approach?

I've been comparing performance times myself and it seems like BFS is consistently and significantly faster.


texts: How can a 64KiB computer do the same task as a modern computer?

texts:
I took an extremely interesting intro to CE course, learning about transistors/memory/logic gates up to LC-3 assembly. Something that was really interesting to me was learning about how a processor's frequency is its speed, determined by the clock signal (if anyone can point to a link of how a clock cycle is made/works or explain, highly appreciated) but my main question is about his claim that any turing-complete computer can accomplish the task of another - performing the same binary operations, just in different amounts of time - that the processor doesn't matter. This depends on memory, though, right? A modern video game wouldn't be able to run on a 64 KiB computer, so I'm wondering if when the textbook and my prof make that claim, it's simply referring to the frequency of the clock cycle (and assuming unlimited/uncapped memory).
Thanks!


texts: Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

texts:
Consider a set $P$ of $N$ intervals $\{I_i = (l_i, r_i)\}$ partially ordered according the standard interval order: $I_i < I_j$ iff $r_i \le l_j$.

I want to find a minimum cardinality partition of $P$ into chains. By Dilworth's theorem, the cardinality will equal the maximum cardinality of any antichain. We can find such a maximum antichain in $O(N\log N)$ time: note that $I_i$ and $I_j$ are incomparable iff $I_i\cap I_j \ne \emptyset$, and applying Helly's theorem in one dimension, deduce that any antichain has nonempty overall intersection, and hence any maximal antichain $A$ is exactly the set of intervals containing $x$ (let us call this $A(x)$) for some point $x$. So it is sufficient to find a point $x$ that maximizes $|A(x)|$. After sorting the endpoints this can be done in $O(N)$ time.

I'm having trouble getting the dual partition though. We can find an optimal partition in $O(N^{2.5})$ time using Hopcroft-Karp to compute a maximum bipartite matching, but it seems like it should be possible to get close to linear time in this case using the duality between antichains and chain partitions. Unfortunately staring at the Wikipedia pages for Dilworth's and Kőnig's theorems doesn't seem to be getting me anywhere.


texts: Help me understand the logic behind x - y in binary by boolean?

texts:
x and y are 4 bit signed numbers (2s complement..)

x - y can be obtained by:

!(!x + y)

I know that in 2s complement

-y = (!y + 1)

So I can pretty much understand how this works:

x - y = x + (!y + 1)

But, what sort of magic is going on in here, how does this work:

!(!x + y)

I mean, when I do the math with pen and paper all is fine, but I do not know why it is working..


texts: Shortest path that can be split into contiguous segments of 5 edges connecting 6 distinct nodes in an unweighted graph

texts:
The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics:

Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. They start in city $1$ and wish to end in city $N$.
All of them love driving, so they move in the following fashion:

Each day, they start in the city they ended at the previous day (city $1$ on the first day) and follow a path consisting of exactly five roads (i.e. they visit six cities and the first visited city is the last visited city of the previous day).
They may visit a city multiple times across multiple days, but they may not visit a city multiple times in the same day.
They can't stop in the middle of the path: if they visit city $N$ after using $k < 5$ roads on some day, they can't end their trip.

Find the shortest path needed to complete this road trip, or determine that it isn't possible. In the case that there are multiple shortest paths, find the lexographically smallest one when looking at only the sequence formed by the ($5k+1$)-th cities visited on the path (i.e. city $1$, ..., city $N$)
$N \leq 10^5$ and $M \leq 5 \cdot 10^5$.

The official problem statement can be found on the contest website (day 2 problem 2).
I haven't been able to find an efficient solution to this problem (from both asking others and searching online), and nobody solved it in the contest. I currently have no idea how to even approach it.
Is there an efficient algorithm to solve this problem, perhaps even for $k$ friends instead of five friends? Since $N$ and $M$ are so large, the algorithm should be linear or linearithmic (when implemented in C++, the code should run for at most 1s in the worst case).


texts:
Suppose given a binary search tree $T$ with $n$ nodes with depth $h$.
We did $n$ times search with cost $c_i$ for search $i^{th}$ search on
$T$ ,and $\sum_{i=1}^{n}c_i=O(n\log n)$. what we can say about $h$?

I think $h=O(\log n)$, but instructor say it's not true.


texts:
Given a semigroup is it possible to give a total order to it?

If not possible in the general case then what about the case of finitely generated finite semigroups?

Does there exist a natural extension of the syntactic order given to a semigroup w.r.t. an upper set? (currently it only induces a partial order)


texts: Is FOL representation of probabilistic assignment statement correct?

texts:
For instance, $x = x + 1[0.3]x+2$ sets $x$ to $x + 1$ with probability $0.3$ and to $x+2$ with probability $0.7$.

If I use notation used in the paper "An Analysis of First-Order Logics of Probability" of Joseph Y. Halpern.

Given a formula $\varphi$ in the logic, he also allows formulas of the form $W_x(\varphi)\geq  1/2$, which can be interpreted as "the probability that a randomly chosen $x$ in the domain satisfies $\varphi$ is greater than or equal to 1/2".

Is my representation of the above probabilistic assignment presented below correct?

$W_x(\varphi_1)\geq 0.3 \land W_x(\varphi_2)< 0.3$ where $\varphi_1$ is $x=x+1$
and $\varphi_2$ is $x=x+2$

Please guide me in this regard?


texts:
I would like to convert 0,347 and 0,9828 to binary, how can I do that?

I know that sucessive multiplication by 2 can do this, but this method seems very painful and even ineffective since the size of count.

This is for a question, and I think that sucessive multiplication is needed. But, in 0,347, I did more than 20 multiplication and did not reach result. Is this normal?


texts:
I am currently working on CLRS 1.13. The idea is to use Stirling's
approximation to prove that
$${2n \choose n} = \frac{2^{2n}}{\sqrt{\pi n}} \left( 1 + O \left( \frac{1}{n} \right)  \right)$$
Now directly replacing Stirling's approximation I arrive to something like:
$${2n \choose n} = \frac{2^{2n} \left( 1 + \Theta(\frac{1}{2n}) \right)}{ \sqrt{\pi n} \left(1 + \Theta( \frac{1}{n}) \right)^2 }$$
Now the quotient is a function that ends up being $O(\frac{1}{n})$ because we
have terms in $O(\frac{1}{n})$ and $O(\frac{1}{2n})$.  The problem is that even if there
is a quotient of two functions that are $O(\frac{1}{n})$.
I don't know if the result is still $O(\frac{1}{n})$.  In fact I haven't seen
any general rule for the quotient of two big $O$ s.
Is there a general rule that I can apply here?


texts:
In "More Is Different," an article about reductionism in science, the author makes the following off hand remark near the end:

  I find that at least one further phenomenon seems to be identifiable and either universal or remarkably common, namely, ordering (regularity or periodicity) in the time dimension... [It] is noteworthy that all computing machines use temporal pulsing.

As far as Turing machines go, this is true since there is a fundamental "time step" during which a symbol is read, the state is changed, and the read/write head moved.  But this got me wondering: are there any non-Turing computing proposals without this fundamental time step?


texts: For every two decidable languages There is a turing machine that decides if they are equal

texts: I was wondering if this is true. I already proved that it is true for regular languages and I assume it is similar in context free languages (correct me if I am wrong), but what about languages in R that are not context-free?


texts:
Does every 3CNF propositional formula has an equivalent 2CNF propositional formula?

Definitions:

3CNF propositional formula is conjunctive normal form propositional formula, which is just conjunction $\land$ of clauses, where each clause is disjunction $\lor$ of at most 3 literals, where each literal is just boolean variable either with or without not $\lnot$ operator/connective.

2CNF propositional formula is conjunctive normal form propositional formula, which is just conjunction $\land$ of clauses, where each clause is disjunction $\lor$ of at most 2 literals, where each literal is just boolean variable either with or without not $\lnot$ operator/connective.


texts: Conjecture about a matrix column swapping challenge problem

texts:
So here is the challenge problem statement: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1512

Basically, given a 0/1 matrix, you need to permute the columns so that the first column is fixed and after the permutation of columns, then for each row the 1's in the row occur contiguously (without counting wrap-around). I thought about this problem and came up with a conjecture that would make it easy to solve, but I'm not sure if it's true.

Conjecture: After the first $k$ columns have been chosen, let $S$ be the set of rows that end with a $1$ in the $k$th column, such that there exists an unchosen column that has a $1$ in that row. Then the $k+1$th column can be chosen to be the column that has (i) 1's for all positions in $S$, and (ii) which has a minimum total number of $1$'s.

Is this true? If so an optimal solution could be constructed very quickly. I know that the $k+1$th column has to satisfy condition (i), which reduces the possibilities, but I'm really hoping we can ensure condition (ii) also holds so that the choice of $k+1$th column is essentially unique.


texts: Note down the possible states in a truth table

texts:
You are required to automate the control of the water tank in your home. There are two water
contact sensors that turn to a TRUE state when in contact with water and a FALSE state when not.
Sensor $1 (S_1)$ to detect water at the maximum level of the tank and sensor $2 (S_2)$ detects water
level at the minimum level. The electronically controlled tap (T) must turn off (FALSE) when the
water level reaches $S_1$ and the tap turn on (TRUE) when the water level drops to $S_2$. There is a
State Register $(S_R)$ which changes state if and only if $S_1$, $S_2$ and $S_R$ are all the same state (i.e. $S_1$
TRUE, $S_2$ TRUE and $S_R$ TRUE then $S_R$ changes to FALSE or $S_1$ FALSE, $S_2$ FALSE and $S_R$
FALSE then $S_R$ changes to TRUE).
My problem is, Consider the output of this system as the state of T. Note down the possible states of this
system in a truth table.
Here the table I did but I am not sure. please tell me If it is correct or not? if it is not please explain right way,
Any help would be greatly appreciate!
$$\boxed{\begin{array}{c|c|c} S1 & S2 &S_R & T(Result) \\[1ex]\hline T & T & F & F \\[1ex] F & T & F & T \\[1ex] F & T & T & T \end{array}}$$


texts: Calculate minimum and maximum Ethernet (IEEE 802.3) frame size from frame format

texts:
According the frame format of Ethernet

Minimum Frame Size should be :

7Bytes + 1Bytes + 6Bytes + 6Bytes + 2Bytes + 46Bytes +4Bytes = 72Bytes

Maximum Frame Size should be :

 7Bytes + 1Bytes + 6Bytes+ 6Bytes + 2Bytes + 1500Bytes + 4Bytes = 1526Bytes

But it is said that the minimum frame size is $64Bytes$ while the maximum frame size is $1518 Bytes$.

How the frame sizes are calculated ?


texts:
Can we define a grammar for the following language?

$$L = \{a^n b^n c^{n+m} | n,m>=0\}\,.
$$

I can define one for this:
$$L=\{a^nb^n|n,m>=0\}
$$

  S --> aSb | λ

or this one:
$$L=\{b^nc^{n+m}|n,m>=0\}
$$

  S --> Ac
  A --> bSc | Sc | λ

but I can't solve the first one, any hint?


texts: Lossless Condensing, Modification, and Decondensing

texts:
Given a string $\alpha$ that is derived from context-free grammar $G$, what is an algorithm $f$ such that there exists a string $\beta$ (derived from an unrestricted grammar) where

$f(\alpha)=\beta$,
$f^{-1}(\beta)=\alpha$,
$\forall \alpha_0,\alpha_1,\alpha_2\in G. d(\alpha_0,\alpha_1)<d(\alpha_0,\alpha_2)\leftrightarrow d(f(\alpha_0),f(\alpha_1))<d(f(\alpha_0),f(\alpha_2))$ where $d(\alpha_0,\alpha_1)$ is the Hamming distance between $\alpha_0$ and $\alpha_1$ (i.e., small perturbations of $\beta$ lead to small perturbations of $\alpha$, and vice versa), and
for any perturbation $\beta'$ of $\beta$ (say, by substituting a letter) we have $f^{-1}(\beta')=\alpha'$ such that

$\alpha'$ is a string derived from $G$ (i.e., "valid" w.r.t. $G$) and
$\alpha'$ is a perturbation of $\alpha$.

On a high level, I would like translate arbitrary modifications to some "dense" representation of a string $\alpha$ into "valid" modifications of $\alpha$ ("valid" means that $\alpha'\in G$).

Since arbitrary modifications of $\beta$ yield valid modifications of $\alpha$, we can say that $\beta$ is a "condensed" representation of $\alpha$, $f$ is the "condensing" operator, and $f^{-1}$ is the "de-condensing" operator.

It doesn't necessarily need to be complete such that all valid modifications of $\alpha$ can be generated but it should be sound such that only "valid modifications of $\alpha$ can be generated.

My first idea was to conceptually index each string that can be generated by $G$. For instance, if $\alpha$ has index $\beta=12$, we could generate a perturbation $\beta'=15$ and find $\alpha'$ as the string derived from $G$ with index 15. However, $\alpha'$ may be very different from $\alpha$ e.g., in terms of Hamming distance and I would need to establish an order over all strings and be able to enumerate the first $n$ strings.

Any ideas or pointers?


texts: Does canonicity imply weak normalization?

texts:
Context: type theory.
My understanding of:

WN: every term can rewrite to NF.
Canonicity: every term rewrites into canonical form.

Then it leads to an intuition where if canonicity holds, then we get NF = canonical form and therefore WN holds. However, I don't see people state this often, like this question talks about canonicity but never mentions NF or normalization. On nLab, canonical form is said to be normal form, which justifies my "NF = canonical form" guess but it doesn't say WN therefore holds. Therefore I'm doubting my intuition.
So, I wonder if it's right (is there a proof?), or if it's wrong (is there a counterexample?).


texts:
I am trying to prove (without converting it into Automata, through just simplification) that the following two regular expressions are equal:

$ (\epsilon + 0^*1^+0)^* = \epsilon + (0+1)^*10 $

here is what I have got so far:

$$ (\epsilon + 0^*1^+0)^* = \\
  (0^*1^+0)^* = \\
  (0^*1^*10)^* = \\
\epsilon + (0^*1^*10)^+ = \\
\epsilon + (0^*1^*10)(0^*1^*10)^* = \\
\epsilon + 0^*1^*10(0^*1^*10)^*$$

I seem to be stuck, I am not sure if I am doing it the correct way, or if there is a better way to prove this.

I know that $(a+b)^* = (a^*b^*)^* $ is true and I think this will certainly come in handy for the problem above but I am not sure how to prove $(a+b)^* = (a^*b^*)^* $ either.


texts: Find equivalence classes of language $L = \{0^n1^n, n \in \mathrm{N}_0 \}$

texts:
I'm asked to find all equivalence classes of the language

$$L = \{0^n1^n, n \in \mathrm{N}_0 \}$$

We have the following definition:

$$(xR_Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \Leftrightarrow yw\in L)$$

As I understand, words $x$ and $y$ belongs to different equivalence classes if $\exists z \in \Sigma^*: xz \in L$ and $yz \notin L$ (or viceversa).

The language L above is not regular so it has infinitely many equivalence classes under $R_L$. In order to differentiate between two classes, I was thinking about defining the equivalence relation in the following way:

$$xR_Ly = \text{"}x[n] = y[n] = 0\text{ and }x[n+1] = y[n+1] = 1\text{"}$$

with $x[k]$ I mean the $k$-th letter in $x$. Under this "approach", all equivalence classes are generated by taking $n$ to be any number $\in \mathrm{N}_0$.

Under my attempt I have the following questions:

In the definition, nothing is said about $x$ and $y$ in $(xR_Ly)$. Do I have to assume that those are two arbitrary words that are already in $L$? (If not, then my approach doesn't work).

For a fixed $n \in \mathrm{N}_0$ I think $\exists$ just one word in the class $C_n$. Then does it mean that the unique word in $C_n$ is only equivalent to itself?

I think I'm not even close to the answer, so would appreciate any help with this.


texts:
I have a grammar,

$L \to A \langle A \rangle^*$

$A \to () \mid (L)$

but I am not sure how to generate parser for $\langle A \rangle$. I know in other case, for example, if $E \to T \langle^*T\rangle^*$ then I can create parser like

proc E begin
  T;
  while symbol='*' do
    T
  od

However in my case don't have any symbol. So how can I check symbol for while process? Or my grammar is incorrect?


texts:
I read on Wikipedia that unification is a process of solving the satisfability problem.

At the same time, I know that such solvers are called "SAT solvers" or "SMT solvers". So, are they different names for the same thing?

If you say that they are different, please point out a flaw in my treatment.


texts: How to remove 'skip' edges from a DAG? (How to find only the longest path from each node to each of its sinks?)

texts:
In two separate projects, I have come across this problem and I still don't have a good solution for it, so I thought it was worth describing here. Consider the following problem:

I have a set of strings that appear in a corpus with their counts. I would like to merge the counts into any substrings that also appear in the corpus.

Here's a close, but incorrect example to demonstrate it. We create a directed graph of strings, where an edge exists from each node to each of its substrings. We then sum counts in topological order.

counts = {"hi":1, "hillo": 1,  "hillotoo":1, "hillotoothree": 1, "what": 1}

graph = nx.DiGraph()
graph.add_nodes_from(counts.keys())

for str1, str2 in combinations(graph.nodes, 2):
    if str1 in str2:
        graph.add_edge(str2, str1)
    elif str2 in str1:
        graph.add_edge(str1, str2)

for node in nx.topological_sort(graph):
    for neighbor in graph.neighbors(node):
        counts[neighbor] += counts[node]

In the end, 'hi's count should be 4, hi + hillo + hillotoo + hillotoothree. However, this code produces:
{'hi': 8, 'hillo': 4, 'hillotoo': 2, 'hillotoothree': 1, 'what': 1}, because there's many more paths to 'hi' that get exponentially summed. This is because with substrings, there is a direct edge from every string to every one of its substrings by definition. Instead, I need to sum counts from each node to the next smaller substring on each path from that node to a sink in the graph, and remove/avoid "skip" edges from nodes to nodes further down paths to a sink.

(NOTE: This simple string example actually has a straightforward solution: copy the counts first, and only add the original counts to the new ones. However, this works only because there is a direct edge from every string to every one of its substrings, so this solution sidesteps the graph entirely. In the general case, this assumption does not hold. There, we do need to sum along paths, but only along the longest path from each node to each of its sinks, without taking any "skip" edges to avoid overcounting.)

Have a crack at this! Thanks.


texts: AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable?

texts:
Suppose We Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm?

According to This Link and to Wikipedia's description of AC3: once one domain is empty, the algorithm stops, indicating there is no solution to the CSP.

This book says: if one domain of the non assigned variables becomes empty then backtracks to....

My challenge is about the behavior of this algorithms, i.e, in which
phase (when) AC-3 stops, and when it's select Backtrack.

  Update: Anyone could describe the behaviors of AC-3 on empty domain in
  each phase?

References: This question asked 5 month ago on SO but I think the answer is wrong, because I add some references that shows other things.


texts: Help with finding a flaw in argument simulating large Turing machines with smaller ones

texts:
I have an argument which, if it goes through, just about proves that either:

Programming languages are more powerful than Turing machines
The busy beaver function ($BB()$) on Turing machines is computable

Now, I understand that it's vastly more likely that my argument has some flaw that I can't find.  But it's more interesting to me how I'm wrong, rather than whether I'm wrong.
Argument
Construct a Turing machine $M_1$ as which takes as arguments (on the tape) $n, k$, simulates all Turing machines with $n$ states until $k$ of them halt, and then halts itself.  This is easy to write in a programming language, as demonstrated by the following Python snippet:
def M1(n, k):
    all_machines = generate_turing_machines(n)
    is_halted = [0] * len(generate_turing_machines)
    while sum(is_halted) < k:
        for (i, machine) in enumerate(all_machines):
            machine.step()
            if machine.is_halted():
                is_halted[i] = 1

Now, let $m_1$ be the number of states required by $M_1$.  Fix $n$ much greater than $m_1$.  Let $k_1$ be the largest number such that $M_1(n, k_1)$ halts and $k_0$ be the smallest number such that when $M_1(n, k_0)$ halts, $k_1$ simulated Turing machines have halted (as all equivalent machines will halt on the same step).  Choose $k$ with $k_0\leq k\leq k_1$.  This means that $M_1(n,k)$ halts in about $BB(n)$ steps.
Construct $M_2$ which is the same as $M_1$ except the first thing it does is write $n$ and $k$ to the tape.  Let $m_2$ be the number of states required by $M_2$.  Then $m_1+K(n)+K(k)+C=m_2$ for some small $C$ (which is probably constant and likely $0$), with $K(n)$ being the Kolmogorov complexity of $n$ in Turing machine states.
Now, $K(n)$ is at most $O(\log(n))$.  There are about $n^n$ machines with $n$ states, so $k$ is about $n^n$, and thus $K(k)$ is at most $O(\log(n^n))=O(n \cdot \log(n))$.  That means that $m_2>n$.  But here we have a problem: if $k$ is easier to write to the tape (so that $K(k)<n-\log(n)$), then $m_2$ would be slightly smaller than $n$.  That would mean $BB(m_2)>BB(n)$ and $m_2<n$, a clear contradiction.
In my mind, these are the possible resolutions:

$M_1$ is impossible to create as a Turing machine, meaning that Python is more powerful than Turing machines are.
There is some transfinite extension to Turing machines which is not much more powerful than Turing machines in general, and $M_1$ can be written in this extension.  In other words, $M_1$ is the limit of a set of machines $M_{1,N}$, each of which can handle any $n<N$.  This would probably entail the busy beaver function being computable.
There is a large set of numbers which cannot be written by a Turing machine in much fewer than $\log(k)=n$ states (we need $K(k)<n-\log(n)$).  It seems impossible to me that no candidate for $(n, k)$ could be sufficiently compressed.

Where is the error in this logic?

I had previously said that $K(k)\leq O(n)$, but @6005 pointed out that was suspect.  With that fixed (to $O(n \cdot \log(n))$), it still seems very surprising to me that we can't achieve a reduction from $K(k)\approx n \cdot \log(n)$ to $K(k)<n-\log(n)$ for any potential value of $(n,k)$, but no longer inconceivable.


texts:
I'm having trouble thinking about the following. If we have two machines 1 and 2 that evenly split a set of data points, does $k$-means separately, then averages the result, does this agree with just $k$-means on one machine?

To be more specific, consider the following routine:

  Split an input dataset evenly between 1 and 2.
  Initialize $k$ centroids that are the same on both 1 and 2.
  Use $k$-means algorithm to find updated centroids.
  Find a new set of $k$ centroids by averaging the corresponding centroid from 1 and 2.
  Loop over 2.

Will this agree with just running $k$-means? I think that it is the averaging part that might work, but then I'm not sure if this routine finishes running.


texts: Is the universe problem for one-counter automata with restricted alphabet size undecidable?

texts:
Consider the following universe problem.

  The universe problem. Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^*$.

In [1], it is stated and proved that the universe problem is undecidable for a particular class of one-counter automata. This result then follows for the class of all non-deterministic one-counter automata. I'm wondering if it is known whether this problem is still undecidable when we restrict the size of the input alphabet of the automaton.

I think that with alphabet size 1 the problem becomes decidable, but what about size 2? And if that turns out to be decidable what is the smallest value of $n \in \mathbb{N}$ such that the problem is undecidable.

I think it's probable that the answer to this question is known but I'm having trouble finding an answer. If it is already known then I would appreciate a reference.

[1] Ibarra, O. H. (1979). Restricted one-counter machines with undecidable universe problems. Mathematical systems theory, 13(1), 181-186


texts: Time complexity of sum of $2^n$ values of polynomials

texts:
First a simpler question: let $q_{1}(k),\dots,q_{n}(k)$ be $n$ polynomials of degree smaller or equal to $n$.

Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = \sum_{i=1}^{n}q_{i}(n)$.

Assume also $0\leq f_{i}(n)\leq n$.

What is the time complexity as a function of the input size for calculating $f(n)$ by the above definition?

I'm not quite sure how to approach this, but my current guess is as follows:

I know evaluating a polynomial is $O(n)$ time, where $n$ is the degree of the polynomial.

I know adding two integers is $O(n)$ where $n$ is the number of bits of the larger integer.

Every try to calculate this seems to get stuck, as i'm getting confused between the time complexity by input size and by actual size (the number itself).

after understanding this, i would like to understand the calculation for time complexity as a function of the input size for a similar problem:

Let $q_{1}(k),\dots,q_{2^n}(k)$ be $2^n$ polynomials of degree smaller or equal to $2^n$.

Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = \sum_{i=1}^{2^n}q_{i}(n)$.

Assume also $0\leq f_{i}(n)\leq 2^n$.

Thanks for any help, i hope this is well enough defined.


texts: IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary?

texts:
The SUBSET SUM decision problem consists of poitive integers a1,...,an; b.
We wish to know if for some subset S of the indices, $\sum_{i \in S}a_i = b$

I want to prove that if b is given in unary(and the ai's are gives in binary), that this decision problem is in P


texts: How can blank be written on the tape if it is not part of input alphabet?

texts:
I have read that input alphabet of Turing machine is subset of tape symbols because in input alphabet we don't allow blank symbol. But when ever there is a transition to final state the transition as (Blank,Blank,R/L) (First parameter here is input,second is what machine will write on tape,third is direction).It means whenever we have processed input,we will read Blank and replace Blank by Blank and goto final state.But how can blank be written on the tape if it is not part of input alphabet?

With this knowledge I am trying to answer the following statement

"It is decidable that Turing machine will print some non blank character
".

Because Turing machine will always write something on the tape so it should be decidable. But is it possible that there are only two states and there is only one transition as "(Blank,Blank,R/L)"?


texts: What would be a not arithmetically definable language that is not Turing reducible to another given not arithmetically definable language?

texts:
I have this question I'm struggling with.

Let $A=\{<i,n>|\;n \in \phi ^{(i)}\}$. In other words, $A$ is the language defined by the set of all pairs $<i,n>$ such that $n$ is $\leq_m$ to the $i$th Turing jump.
A is definitely not an arithmetically definable language, and you can prove this by contradiction.

I have to find a language, let's say $B$, that is more complex than $A$ $i.e.$ $B\nleq_T A$. I thought about $B=\{<i,n>|\;n \not\in \phi ^{(i)}\}$, but I'm not sure about my reasoning, I think an oracle turing machine with an oracle $A$ couldn't reduce to $B$..

And one last thing, do you think there exists a language that is more complex than any other (it doesn't reduce to anything)?

If you have any hints that could help me solve those two questions I would be really grateful!


texts:
There are known algorithms to find the connected components of a given graph.  Those I know are easily extensible to support addition of nodes and edges to the graph and then find the resulting components more quickly than by recomputing from scratch.

What I'm looking for is an algorithm with an associated data structure which allow the efficient determination of connected components after removal of nodes and edges.


texts: Distributed algorithms - $\alpha, \beta$ synchronizers

texts:
I experience a difficulty in solving exercises in distributed algorithm. Below is the the exercise I try to solve, it looks like I miss basic idea.

Exercise. Consider a 15-processor asynchronous network with processors 0,…,14. The processors constantly run a synchronizer. Let $v$ and $v'$ be two processors in the network, and suppose that at a certain moment, the pulse counter at $v$ shows $p=27$. What is the range of possible pulse numbers at $v'$ in each of the following cases:

a) The network is a ring, $v$ is processor number 11, $v'$ is processor number 2 and the synchronizer used is $\alpha$.

Idea: if $v'$ hasn't sent any message up to pulse 27 of $v$, pulse of $v'$ is still 0, therefore lower bound of pulse of $v'$ is 0. The model of synchronizer is $\alpha$ it means every node informs all nodes about it's safe(v,p) state, hence I assume that $v'$ might be 11-2=9 pulses before $v$.

b) The network is a full balanced binary tree (4 levels), $v$ is the root, $v'$ is one of the leaves and the synchronizer used $\beta$.

Idea: $v'$ also might have pulse 27, in this case $v$ sends at speed of $v'$.

c) The same as in (b), except both $v$ and $v'$ are leaves.

Honestly, I am completely confused by this exercise, I wrote few ideas, but I don't have any understanding and any intuition behind the answers.

I will appreciate if someone show me the way how to solve such exercises.


texts:
How come O(n) + O(logn) = O(logn)?

When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is O(logn). It doesn't make sense to me since n is bigger than logn.


texts: Generating a Context Free Grammar(CFG) from a Language

texts:
I would really appreciate if anyone could tell me how to generate CFG from this language. I am trying to learn the procedure of generating CFGs from CFLs and I am able to solve easier problems.. but I am really stuck on this one, I just can't get it how can I generate at two different positions at the same time.

L = {0^i 1^j 0^k | i + j >= 2k }


texts: Making random sources uniformly distributed

texts:
How do I build a random source that outputs the bits 0 and 1 with $prob(0) = prob(1) = 0.5$. We have access to another random source $S$ that outputs $a$ or $b$ with independent probabilities $prob(a)$ and $prob(b) = 1 - prob(a)$ that are unknown to us.

How do I state an algorithm that does the job and that does not consume more than an expected number of
$(prob(a) \cdot prob(b))^{-1}$ symbols of $S$ between two output bits and prove its correcteness?


texts:
There is a definition of integer representation:

  A positional representation for integers that uses the binary digits 0
  and 1, in which the values represented by successive bits are
  additive, begin with 1, and are multiplied by successive integral
  power of 2, except perhaps for the bit with the highest position.
  (Adapted from the American National Dictionary for Information
  Processing Systems.)

It is not clear to me. Could you give an example reflects that definition? In general, I don't understand what is the successive integral power of 2 and what is the succesive bits?


texts: On proving NP-completeness by reduction to 3-partition problem

texts: Consider a problem $X$ can be reduced to 3-partition problem. So, when 3-partition has a solution then $X$ has a solution. But if 3-partition does not have a solution, they $X$ may or may not have a solution. In this case, is it legal to say that the problem $X$ is np-complete?


texts: Is there a programming language that is not a formal language

texts: Are out there, any programming languages that are not defined algorithmically so that we can call them "constructed languages" but not "formal languages"? Are there any discussions or papers on that topic? It seems pretty hard to develop a compiler for this kind of languages.


texts: Given N vertices and M edges find if two nodes are in the same connected component?

texts:
Given a set of $n$ people and $m$ friendship relations between those people (relation is between two persons) we need to suggest a data structure that supports the division of those people into maximum groups such that if 2 people are connected, they belong to the same group.

Asking $k$ queries, where each query is asking if $(i,j)$ are 2 people are in the same group, what data structure can have a total running time of $O(m+n+k)$?

For example:

$n = \{1,2,3,4\}$

$m = \{(1,2) , (2,3)\}$
(person 4 has no friends)

So the above relations will form 2 groups:
$\{1,2,3\} ,\{4\}$

I thought about taking an Undirected graph and checking if two vertices are in the same connected component. The problem is that I do $k$ checks. And I need to find a way such that a check will be $O(1)$.


texts: Is summing a function over all subsets in PP?

texts:
Consider the following decision problem:

Input: a set $X = \{x_1, \ldots, x_n\}$, a mapping $f \colon 2^X \mapsto \mathbb{N}$ such that for $f(Y)$ is computed in polynomial time for any $Y \subseteq X$, and an integer $k \in \mathbb{N}$.

Question: does $\sum_{Y \subseteq X}{f(Y)} \geq k$ hold?

Is this problem in the complexity class $\mathsf{PP}$? If yes, which NP Turing machine decides it?

Additionally, for proving such a membership result:

Should we specify how $f$ is represented?
Should we assume that $f$ is polynomially bounded?


texts: As in title. Does $NSPACE(n) \subseteq DTIME(2^n)$ ?


texts: What does it mean to isolate a field in a word?

texts:
I have been reading in the 'computer organization and design' book and I encountered this section:

what operations isolate a field in a word

I know that the answer is logic operations and shift instructions from the book but.
I want to know what does it even mean to isolate a field


texts: A special case for the subset sum problem

texts:
If we wanted to see if any disjointed subset of a set $X = [w_1, ..., w_n]$ exists such as the sum of its elements equal exactly a given value $M$ (0-1 Knapsack problem) we could employ a DP solution or a simple greedy algorithm.

A simple implementation of which could be the following. Sort the set $X$ in non-decreasing order and try taking taking the values of $X_{sorted}$ one by one only if said number is smaller than the difference of $M$ with the sum of the currently selected numbers. By the end of it we should be able to see if it is possible to form the number $M$ using a combination of that set. This will of course not work all the time.

My question is, how things would change if we knew that the numbers $w_1, w_2$ and so on are in fact guaranteed to be multiples of 2. Would then be another way to check if any given integer $M$ can be formed or not with a combination of those numbers?


texts:
How different are string matching and integer matching in terms of time complexity?

I'm asking this especially in relation to Rabin Karp algorithm. Why is it faster to compute hash code for every substring and check for equality of hashcode with the hashcode of the given string than the naive method of just checking if amy of the substrings match with the given string?


texts: How to determine offset bits when addressing CPU cache?

texts: I know that the offset is based off of the line size for a cache. I have seen the example: "32-btye line size would use the last 5-bits (i.e. 25) off the address as the offset into the line" but I do not understand the process used to determine this.


texts: How do I do sum of first k elements of a row of a Pascal's Triangle efficiently?

texts:
More specifically, I want to:

$^nC_0 + ^nC_1 + ^nC_2 + ..... + ^nC_k$

I tried doing it linearly by calculating $^nC_{j+1}$ by multiplying $^nC_{j}$ with (n-j+1)/j.

The answer it gives is correct for small numbers. Since n and k can be large, I need have keep modding with P, a given prime number.

My method fails since I have to divide with j, which breaks the mod.
Any suggestions?


texts:
Suppose you have an undirected graph $G = (V, E)$, known to both Alice and Bob, Alice gets an independent set of $G$. Bob gets a Clique $B ⊆ V$.

Is there any algorithm in $O(\log^2 n)$ bits that finds whether
$ A ∩ B = Ø $?

This is a well known communication complexity problem called CIS problem that was described by Yannakakis.

Lecture notes; the claim is Theorem 3
Link to Nisan & Kushilevitz's textbook

I'm not sure why and how does this work exactly. and which part of the $n/2$ vertices are reduced by both players.

P.S. I came to a conclusion that an independent and a clique can intersect in at most one vertex.


texts: How undecidable is it whether a given Turing machine runs in polynomial time?

texts:
The proof of Theorem 1 that PTime is not semi-decidable in this recent preprint effectively shows that it is $\mathsf{R}\cup\mathsf{coR}$-hard. The proof itself is similar to undecidability proofs at  cs.SE and cstheory.SE. However, what is different is a footnote, which highlights that proving both $\mathsf{R}$-hardness and $\mathsf{coR}$-hardness seems to be new:

  1The undecidability of PTime seems to be folklore, but non-semi-decidability seems to be new, even though semi-decidability is a natural property here.

But I want to ignore the question whether this observation is new. What interests me is what is known about the degree of undecidability of PTime. For example, is computation in the limit powerful enough to decide PTime? Are there better lower bounds than $\mathsf{R}\cup\mathsf{coR}$ for the difficulty of PTime?

Note: I denote the problem to decide "whether a given Turing machine runs in polynomial time" as PTime here. I know that this is incorrect, because PTime is a class of languages and not a class of Turing machines. However, I found this misuse of terminology convenient for this question.


texts: Implications of the class of problems with parallel solutions being not P-complete for optimization of matrices

texts:
I am not a specialist on computational complexity theory. I do work on optimization and I am currently researching about the implications of the class of problems with parallel solutions (NC) being not P-complete, i.e., NC$\neq$P for optimization. In particular, I am interested about the consequences for equations based on matrix optimization problems.

For instance, given a square matrix $A$ find a positive definite matrix $M$ with same dimensions and such that $AM+MA^\top$ is negative definite.

Could someone elaborate on the difficulties to make a parallel algorithm, assuming that NC$\neq$P, to verify the negativeness of $AM+MA^\top$? Also, could someone provide a reference (article or book) that contain a similar explanation?

Thank you

Ps.: I also started to read the book [1] but, since I am not a specialist on complexity theory, I cannot grasp the details regarding the limitations explained by the authors. I understood that there are evidences suggesting that NC$\neq$P.

[1] Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo "Limits to Parallel Computation: P-Completeness Theory", Oxford University Press


texts: What does the symbol # mean when it comes to languages

texts:
Given the following:

$$\{ w\#x \mid w^R \text{ is a substring of $x$, with $x$ and $w \in \Sigma^*$} \}$$

What does $w\#x$ denote?


texts: Language consisting of all Turing machine encodings

texts:
$A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ }

What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL?

I would say $A$ is decidable since we can write an algorithm to check whether a string is a valid encoding of a Turing machine .

But, is $A$ Regular[or CFL or CSL] ?

Edit : Someone argued that he could make an encoding where all the possible strings(What would be the alphabet here?-same as the encoding I suppose) are valid encoding of a TM(since there is a one-to-one correspondence between two countable infinite sets), hence making $A$ regular .


texts: Looking for a good algorithm to divide the nodes of a complete graph into groups

texts:
I have a set of locations, around 100, I want to divide into groups.

I say these locations are in a graph because the geometric proximity (straight line distance) doesn't matter to me, and I have a matrix of the distance (non straight line distance) and time, that would take to travel from any location to another. Either one, time or distance, can be used as edge weights for this complete graph.

The idea is to assign a group of locations to a person that will visit the locations in it, (there is no obligation to do a traveling salesmen or visit them in a specific order or to avoid passing on a repeated node).

Ideally these groups have a minimum of 8 locations, and a maximum of 11 locations. (For simplicity maybe a set amount of 10 per group would suffice).
And I want to minimize the sum of weights needed to visit all the nodes in a group at least once.

All locations must belong to one group, and only one group.

Where do i go from here?
I'm kind of rusty on graph theory. Is there a good algorithm for this already? It doesn't need to be optimal and I do understand that this will probably be an NP hard problem and not very efficient.
Because i'm treating it as a graph i keep finding graph algorithms but most i find are not suited for weighted graphs or complete graphs.


texts: Proving the small-step semantics of factorial program

texts:
I am given the following command $C$:

$y:=1;$
while $\neg (x=1)$ do
$y:= y*x;$
$x:= x - 1$.

I have to show that $[\![ C ]\!]_s(s) = \{x \mapsto 1, y \mapsto s(x)!\}$ if $s(x) \geq 1$ and undefined otherwise. Where $[\![ C ]\!]_s(s) = s'$ if $\langle C, s \rangle \rightarrow^* s'$ and undefined otherwise.

The proof is by induction on $s(x)$. My problem is to figure out the last step in the induction step. The induction hypothesis is that $[\![ C ]\!]_s(s) = \{x \mapsto 1, y \mapsto s(x)!\}$ for $s(x) \leq k$. For the induction step I assume that $s(x)=k+1$. Using the small step semantics rules I obtain a state $s''' = \{x \mapsto k, y \mapsto (k+1)\}$. Then I can apply the induction hypothesis and obtain $[\![ C ]\!]_s(s) = \{x \mapsto 1, y \mapsto k!\}$. Now I am stuck - can anybody give me a hint on how to arrive at $[\![ C ]\!]_s(s) = \{x \mapsto 1, y \mapsto (k+1)!\}$?


texts: Knapsack dynamic programming complexity issue for $W=1$, is it $O(n)$?

texts:
The 0-1 knapsack problem is given by

$$\begin{align}&\text{maximize } \sum_{i=1}^n v_ix_i,\tag{P1}\\&
\text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } x_i \in \{0,1\}.\end{align}$$

Running the dynamic programming algorithm for this problem would give an optimal solution in $O(nW)$.

If I define $p_i=w_i/W$, I get the following knapsack problem:

$$\begin{align}&\text{maximize } \sum_{i=1}^n v_ix_i,\tag{P2}\\&
\text{subject to } \sum_{i=1}^n p_i x_i \leq 1,\\&\text{and } x_i \in \{0,1\}.\end{align}$$

Running the dynamic programming algorithm for this problem would give an optimal solution in $O(n)$. This is not true, isn't it?


texts: Intersection of two particular languages

texts:
Here's the question:

  Compute the intersection of the following two languages:
  \begin{align}
&L_1 = \{ a^{n+1} b^{2n} a^{n+1} \mid n \ge 0 \} \\
&L_2 = \{ w \in \{a,b\}^* \mid \#_a(w) + \#_b(w) \equiv 1 \pmod 2 \}
\end{align}

I'm pretty sure that $L_2$ is just "$|w|$ is odd", which would mean the intersection of the two languages would be $L_1$ when its length is odd, right?

What I'm confused about is that $|w|$ for every $w ∈ L1$ will always be even no matter what $n$ is.

Can someone help me find the solution? I have absolutely no clue how to do it.

Edit:  #a(w) + #b(w) %2 = 1 not 0 (my bad)


texts: Why irreducibility is an important concept in Flow Graphs?

texts:
Here is a definition of reducible flow graphs :

  A flow graph is reducible if every retreating edge in any DFST for
  that flow graph is a back edge.

And the reasons why we care about retreating/back edges:

  Proper ordering of nodes during iterative algorithm assures number of passes limited by the number of “nested” back edges.
  Depth of nested loops upper-bounds the number of nested back edges.

With this explanation, I have more questions: why number of passes is important? why we want to know upper-bounds?

However, I still do not understand the impact of irreducibility .
Why should we care about it? Will it make it harder to do loop flatten? What if we have irreducible flow graphs for program analysis?


texts: Selecting vertices in a graph in an order to keep border vertices as few as possible

texts:
I am given an undirected graph. Initially all vertices are white. I need to color them black in such an order that the maximum number of vertices which are on the border between black and white regions is minimal. Is there an algorithm to find an optimal order for that?

More formally. We are given an undirected, connected graph $G = (V,E)$ consisting of $n$ vertices. I am looking for a sequence of increasing subsets of vertices $V_0, V_1, ..., V_n$, where
$V_0 = \emptyset$, $V_{i+1} = V_i \cup \{v\}$ for some $v\in V$, and $V_n = V$.
For any subset $W \subset V$ we define a cost function $c(W)$ as the number of "border" vertices, i.e. size of $\{w\in W : \exists m\in V\setminus W: (w,m)\in E \}$. I am looking for such a sequence where $\max_i(c(V_i))$ is minimal.

I feel my problem is somehow related to maximum flow algorithms, the same way as minimum-cut problem is. I think there must be a name for this (or similar) problem. However, as I was mixing "minimal cut" in various ways in the search engines, I was unable to find it.

A bit of context: I have a series of tasks to perform (edges), each loading two files from a disk (vertices). In order to speed up the process, I don't want the reload every pair of files every time. Instead, I want to keep some files in memory so that I can reuse them when another task uses the same file. But I cannot keep all files that there are because of memory constriants. The above sequence would help me select an optimal processing order, keeping the number of active files to minimum.


texts: Why is a subset of a undecidable language decidable?

texts: I have problems with the understanding why a subset of a undecidable language is decidable. We've proved in the lecture that $HALT$$_T$$_M$$=${$<M,w>$|M is a TM and M halts on input w} is undecidable. Can someone give an example of a subset from $HALT$$_T$$_M$ and explain why it is decidable? Is $\Sigma^*$ a valid subset of $HALT$$_T$$_M$?


texts: Is this scheduling problem with arrival times, deadlines, and costs NP-hard?

texts:
There are $n$ jobs where each job $i$ has an arrival time $r_i$, a deadline $d_i$ and a cost $c_i$. The problem is to find a scheduling time $t_i$ (where $r_i\leq t_i\leq d_i$) for each job $i$ in order to minimize $$\sum_i\max_{j\in S_i}(c_j),$$ where $S_i$ is the set of jobs scheduled at time $t_i$.

Can we solve this problem in polynomial-time or is it NP-hard?

For example, if all jobs can be scheduled at the same time $t$, then the objective will be $\max(c_1,c_2,\ldots,c_n)$. The issue is that all jobs cannot always be scheduled at the same time $t$ because of their arrival times and deadlines. If I schedule the jobs as they arrive, I may end up with the objective of $\sum_{i=1}^nc_i$, which is the largest possible. So, the problem is somehow how to partition the jobs into sets $S_i$ (where jobs in $S_i$ are scheduled at the same time) for which we obtain the minimum objective. As such, I am trying to reduce Partition to this scheduling problem but still did not find the right reduction. Do you have any hints?


texts: Is complexity class $\Sigma^1_1$ from polynomial hierarchy decidable?

texts:
It is within polynomial hierarchy so I assumed it is decidable. The picture like this further hinted in that direction.
Yet, in a paper on page 2 I read

  Satisfiability of [...] is highly undecidable (i.e., $\Sigma^1_1$-hard)

which implies that $\Sigma^1_1$-hard is undecidable. Do authors mean something else by "highly undecidable" or $\Sigma^1_1$-hard is really undecidable?
In the latter case, why is it included inside decidable PSPACE?
(or I misunderstanding things...)


texts: Showing that the entropy of i.i.d. random variables is the sum of entropies

texts:
The shannon entropy of a random variable $Y$ (with possible outcomes $\Sigma=\{\sigma_{1},...,\sigma_{k}\}$) is given by
$H(Y)=-\sum\limits_{i=1}^{k}P(Y=\sigma_{i})\;\log(P(Y=\sigma_{i}))$.

For a second random variable $X=X_{1}X_{2}...X_{n}$, where all $X_{i}$'s are independent and equally distributed (each $X_{i}$ is a copy of the same random variable $Y$), the following equation is known to be true:

  $H(X)=n\cdot H(Y)$

I want to prove this simple equation, where the outcomes from $Y$ are interpreted as symbols from an alphabet $\Sigma$ and therefore $X$ is the random variable for strings of length $n$ (based on the distribution of $Y$).

It is easy to see, that
$P(X=w)=P(X=w_{1}...w_{n})=P(X_{1}=w_{1})\;\cdot\;...\;\cdot\; P(X_{n}=w_{n})=\prod\limits_{i=1}^{n}P(Y=w_{i})$
... but my approach to prove $H(X)=n\cdot H(Y)$ seems to be in a dead point
(every word $w$ has the form $w=w_{1}...w_{n}$ with $w_{i}\in\Sigma$ and  let $\large |w|_{\sigma_{i}}$ be the number of occurrences of $\sigma_{i}$ in $w$):

$H(X)=-\sum\limits_{w\in\Sigma^{n}}P(X=w)\;\log(P(X=w))$
$=-\sum\limits_{w\in\Sigma^{n}}\left(\prod\limits_{i=1}^{n}P(Y=w_{i})\right)\;\log\left(\prod\limits_{i=1}^{n}P(Y=w_{i})\right)$
$=-\sum\limits_{w\in\Sigma^{n}}\left(\prod\limits_{i=1}^{n}P(Y=w_{i})\right)\left(\sum\limits_{i=1}^{n}\log\left(P(Y=w_{i})\right)\right)$
$=-\sum\limits_{w\in\Sigma^{n}}\left(\prod\limits_{i=1}^{k}P(Y=\sigma_{i})^{\large |w|_{\sigma_{i}}}\right)\left(\sum\limits_{i=1}^{k}\large |w|_{\sigma_{i}}\normalsize \;\log\left(P(Y=\sigma_{i})\right)\right)$

So, I am able to change some indices from word length to the length of the alphabet, which is used in $H(Y)$. But what now? Any help?


texts: Quickly identify changes in connectivity

texts:
Given an undirected graph with at least one path connecting $u, v$, and a sequence of edges to be removed: $e_1, e_2, \dots$, I would like to quickly identify the point at which $u$ will be separated from $v$. Clearly this could be done by doing a full path search after each removed edge, but this is very expensive.
Is there a faster algorithm? (This is this question which asks about a related but more general and difficult situation, but it has gone unanswered.)


texts: Hash tables for storing data in an application that supports partial search

texts:
Is a hash table a good data structure for storing data in an application that support partial search such as "select * from MyTable where name like 'John%'.  If not, what is?
I would have thought that hash table isnt ideal because there no way to make faster than O(n). Maybe a some kind of balanced binary tree best. However, I am not sure that it would be best for the particular query above.


texts: Reference needed: lower bound on sample size for determining which side of coin is biased with high probability

texts:
I am looking for a reference to see if the following problem has been addressed before.  Suppose we know that a coin is biased with probability $p>\frac{1}{2}$, but we are unsure if the coin is biased for heads or tails.  I want to know a lower bound on a sample size $n$ needed to determine with high probability which side the bias is in favor of i.e. with probability at least $1-\delta$ so the answer would be $n=\Omega(g(p,\delta))$ or something like that.

Thanks for any help!


texts: Proof of the Cook-Levin Theorem - snapshot transitions

texts:
I'm trying to understand the proof of the Cook-Levin thereom in Aurora and Barak's "Computational Complexity" text.

A snapshot $z_i$ of $M$’s execution on some input $y$ at a particular step $i$ is the triple $(a, b, q_i) \in \Gamma \times \Gamma \times Q$ such that $a, b$ are the symbols read by $M$’s heads from the two tapes and $q$ is the state $M$ is in at the $i$th step.

At some point in the proof, it is claimed that $$z_i = F(z_{i-1}, z_{prev(i)}, y_{inputpos(i)}),$$ where

$z_i$ represents a snapshot of the the Turing machine at step $i$ when started on input $y$
$prev(i)$ denotes the last step before $i$ that $M$ visited the same location on its work tape,
$inputpos(i)$ denotes the location of the input tape head at
the $i$th step

The assumptions are that $M$ has only two tapes and that it is oblivious.

My understanding is that on input $y$, the computation of $M$ can be described by a sequence of configurations that tell us the current tape symbols, the current register state. I think the claim is that the next snapshot, $z_i$, can be computed using only $z_{i-1}, z_{prev(i)}, y_{inputpos(i)}$ in our special case. How?

If $z_i=(a,b,q_i)$, then I think we can just set $a = y_{inputpos(i)}$ since $y_{inputpos(i)}$ is the content of the input work tape cell at step $i$. How do we deduce $b$ and $q_i$ from $(z_{i-1}, z_{prev(i)}, y_{inputpos(i)})$?

If $z_{i-1}$ tells us the current snapshot, why is this not sufficient to deduce the next one? Doesn't $M$'s transition function tell us this?


texts: A Query regarding Quadratic Residuocity Problem

texts:
In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:
$$
    x^2\equiv q \pmod{n}.
$$Otherwise, q is called a quadratic nonresidue modulo n.

Problem Definition: Given a constant c, is there a positive integer x < c such that
$$
    x^2\equiv q \pmod{n}.
$$

If n is composite, the problem is NP-Complete, even if given the prime factorization of n. But, if n is a prime the problem is solvable in polynomial time.

Query: In case n is composite, and given that it has lets say exactly 3 distinct prime factors, does the problem still remain NP-Complete? Any link to the references?


texts: How to create an AVL tree, given it's pre-order traversal?

texts:
Given the pre-order traversal, we can easily obtain the necessary Binary Search Tree(BST- not necessarily balanced). However, the problem arises when we have to decide the balancing manually(this was a question in a written quiz). Is it possible to do so in any way?

Edit: I built the BST following the steps in this video: https://www.youtube.com/watch?v=rOiqrg5AH7M. After this step, I proceeding on to balancing the tree following zig-zig and zig-zag rotation(all four possible cases). However, the resulting tree did not have the same preorder traversal.(I unfortunately don't have access to the exact values given in the question, neither to my answer).

My doubt is: how do I obtain the correct AVL tree?


texts:
I'm reading the Digital Design and Computer Architecture by David Harris, Sarah Harris. The authors give the following definition of combinational logic:

A combinational circuit’s outputs depend only on the current values of
the inputs; in other words, it combines the current input values to
compute the output... A combinational circuit is memoryless, but a
sequential circuit has memory. The functional specification of a
combinational circuit expresses the output values in terms of the
current input values.

However, they claim this circuit is not combinational:

because "node n6 connects to the output terminals of both I3 and I4". Indeed, it's one of the designated signs when a scheme can not be combinational but, according to the authors:

Certain circuits that disobey these rules are still combinational, so
long as the outputs depend only on the current values of the inputs.

As I'm able to catch on, the aforementioned circuit is the case: its output is 1 if and only if its inputs are both 1, otherwise the output is 0. So the output is defined as a function of the inputs (the AND function).
In fact, there was already a question about this circuit and it has an accepted answer. Here's an excerpt from it:

Circuit (d) cannot be written in this form [of formula], since the
outputs of I3 and I4 are wired together. What is the relation between
the input to the rightmost gate and the outputs of I3 and I4? Not
something that can be described combinatorially.

Unfortunately, I'm still confused due to

The circuit, regarded as a black box, is still in scope of the combinational logic definition: its output values depend only on the current values of the inputs;
The relation between the input to the rightmost gate and the outputs of I3 and I4 can be described through the function NAND of the circuit inputs and this function is quite "memoryless". It's not obvious  for me why we can't afford to depict a gate input using multiple outputs of other gates.

I need some elaboration. Maybe things would fall into place if someone provide a circuit example when two gates outputs is connected to one input and it actually causes "memory" (in contrast to the considered sample).


texts: What will be T(n) after second step in a Recurrence Relation

texts:
T(n) = 2T(n-1) + n

Using back Substitution at first step we get

T(n) = 4 T(n-2) + 2(n-1) +n

If i go further one more step then what i am getting is

T(n) = 16 T(n-4) + 8(n-3) +4(n-2) + 2(n-1) +n


texts: Calculate how much segements the system can handle

texts:
I am a bit lost calculating how much segments will the system handle in a memory segmented system (without virtual memory). The problem says that the system has a word length of 32 bits and the address are 6 hexadecimal numbers, 3 of them are the segment identifier. We have a segment size of 4KiB

I tought this:

If the address are of 24 bits wide, we could address $2^{24}$ bytes of data and our segment size is $2^{12}$ bytes. So divide them and we have the maximum number of segments our system can handle.

But I was told this isn't the way to solve this problem. Here is the way it's supposedly correct:

We have $2^{24}$ address in our system, with a length of 32 bits so we have $2 ^ {29}$ bits of addressable memory, $2 ^{16}$ KiB of addressable memory. So dividing between our segment size we have $2^{14}$ segments.

But I don't find this answer correct, because if it says that the 3 hex digits identifies the segment we have 12 bits to identify every segment, with a maximum of $2^{12}$ segments, so I don't know how the second solution manage to add 4 times more segments than my solution.

So what answer is correct?

Thanks


texts:
I am trying to find a unary language whose runtime complexity is exponential in $n$ (e.g. $\Theta(2^n)$ or a similar expression). But I am not sure how to reason about the runtime of such languages.

I tried the language: $L_1=\{1^{2^k}\}$. This language can be identified by counting the number of ones in the input into a binary register, then checking if the binary register has only zeros and a leading one. This requires $O(n)$ steps to read the input, and probably $O(\log n)$ for each addition, so the total runtime is $O(n \log n)$. Is this correct?

What about the language: $L_2=\{1^{2^{2^k}}\}$? This language can be identified by counting the number of ones in the input into a binary register, then checking if the number of zeros in the register is in $L_1$. This seems like it can be done in time polynomial in $n$.

How can I construct a unary language that can only be identified in exponential time?


texts: The essential difference between spiking neural networks and earlier generation ANN's

texts:
I have been studying Spiking Neural Networks online from various papers, mainly Maass (1997). I am not entirely sure I understand what makes SNN's pulse-code in contrast to earlier ANNs which are considered rate-code.
I have background in neuroscience so I understand the terms and ratio, I'm asking regarding the actual implementation.

Is the practical difference in the fact that when each neuron updates its current state in an SNN it deals with the entire history of every pre-synaptic neuron and not only the last step? Is that what gives it temporal characteristics which previous generation ANN's lack?


texts: Why isn't there just one "keystone" activation function in Neural Networks?

texts:
This article says the following:

Deciding between the sigmoid or tanh will depend on your requirement of gradient strength.

I have seen (so far in my learning) 7 activation functions/curves. Each one seems to be building on the last. But then like the quote above, I have read in many places essentially that "based on your requirements, select your activation function and tune it to your specific use case".
This doesn't seem scalable. From an engineering perspective, a human has to come in and tinker around with each neural network to find the right or optimal activation function, which seems like it would take a lot of time and effort. I've seen papers which seem to describe people working on automatically finding the "best" activation function for a particular data set too. From an abstraction standpoint, it's like writing code to handle each user individually on a website, independently of the others, rather than just writing one user authentication system that works for everyone (as an analogy).
What all these are papers/articles are missing is an explanation of why. Why can't you just have one activation function that works in all cases optimally? This would make it so engineers don't have to tinker with each new dataset and neural network, they just create one generalized neural network and it works well for all the common tasks today's and tomorrow's neural networks are applied to. If someone finds a more optimal one, then that would be beneficial, but until the next optimal one is found, why can't you just use one neural network activation function for all situations? I am missing this key piece of information from my current readings.
What are some examples of why it's not possible to have a keystone activation function?


texts: Is the expression (λx.xx)(λy.y) typeable in the following system?

texts:
We are given a simple functional language:

$ e ::= x | n | e_{1}e_{2}|\lambda(x:\tau).e$

with types:

$\tau ::= \text{int} | \tau_{1} \rightarrow \tau_{2}| \tau_{1} \land \tau_{2} $

Is the expression $ (\lambda x.xx) (\lambda y . y) $ typeable in this system?

Let's denote $x:\tau_{x}, xx : \tau_{xx}$. I'm rookie in the field and so far I have only dealt with very simple systems where type equations as the one we get for left subterm: $\tau_{x} = \tau_{x} \rightarrow \tau_{xx}$ indicated a term analyzed is not typeable . The type $\tau_{1} \land \tau_{2}$ is something new to me and I don't have intuition what can or cannot be done here.


texts: Recursion problem involving head, tail and xor

texts:
Consider a set of functions:

head(l) returns first bit from list l, e.g.

head([0,1,0]) = 0,
head([1]) = 1

tail(l) returns a list by removing first element from l, e.g.

tail([0,1,0]) = [1,0],
tail([1]) = []

a:l appends bit a to beginning of list l, e.g.

1:[0,1,0] = [1,0,1,0].

xor takes takes as input two bits and returns a bit.

xor(a,b)
if (a == b)
  return(0)
else
  return(1)
endif

f1 takes as input a list and returns another list.

f1(s)
if (s == []) then
  return([1])
else if (head(s) == 0) then
  return(1:tail(s))
else if (head(s) == 1) then
  return(0:f1(tail(s)))
endif

f2 takes as input a bit and a list and returns a bit.

f2(b,s)
if (s == []) then
  return(b)
else if (head(s) == 0) then
  return(f2(xor(b,1),tail(s)))
else if (head(s) == 1) then
  return(xor(b,1))
endif

g1 takes as input a nonnegative number and returns a list.

g1(n)
if (n == 0) then
  return([0])
else
  return f1(g1(n-1))
endif

g2 takes as input a nonnegative number and returns a bit.

g2(n)
if (n == 0) then
  return(0)
else
  return f2(g2(n-1),g1(n))
endif

Can anyone explain what the function g2() returns?

I am able to find out g1() returns a list in binary
for example

g1(1) = [1]
g1(2) = [01]
g1(3) = [11]
g1(4) = [001]


texts:
Is it possible to reverse engineer sorting algorithm (sorting by comparisons) by sequences of indices of compared elements? We can input any lists of numbers arbitrarily many times. Comparison to existing algorithms and their corresponding sequences is not allowed. Further tests can alter algorithm, so task can be restricted: use only limited number of test sequences and find one of simplest algorithms which match corresponding indices.

EDIT:
Example:
This is full tree of comparisons for n = 4. Tuple (0, 1, -1, 0) means that second element is larger then third. I forgot to mention that all comparisons are strict. Start of tree reads so: First element is larger than second, third larger than fourth, second larger than fourth, second larger than third. That's all, we have sorted sequence. By not allowing comparison to existing algorithms I assume that we have some new algorithm (this tree does not represent it), which have different sequence of comparisons. Actually my problem not about sorting at all, I just chose appropriate analogy.

(1, -1, 0, 0)
  (0, 0, 1, -1)
    (0, 1, 0, -1)
      (0, 1, -1, 0)
      (0, -1, 1, 0)
        (1, 0, -1, 0)
        (-1, 0, 1, 0)
    (0, -1, 0, 1)
      (1, 0, 0, -1)
        (1, 0, -1, 0)
        (-1, 0, 1, 0)
      (-1, 0, 0, 1)
  (0, 0, -1, 1)
    (0, 1, -1, 0)
      (0, 1, 0, -1)
      (0, -1, 0, 1)
        (1, 0, 0, -1)
        (-1, 0, 0, 1)
    (0, -1, 1, 0)
      (1, 0, -1, 0)
        (1, 0, 0, -1)
        (-1, 0, 0, 1)
      (-1, 0, 1, 0)
(-1, 1, 0, 0)
  (0, 0, 1, -1)
    (1, 0, 0, -1)
      (1, 0, -1, 0)
      (-1, 0, 1, 0)
        (0, 1, -1, 0)
        (0, -1, 1, 0)
    (-1, 0, 0, 1)
      (0, 1, 0, -1)
        (0, 1, -1, 0)
        (0, -1, 1, 0)
      (0, -1, 0, 1)
  (0, 0, -1, 1)
    (1, 0, -1, 0)
      (1, 0, 0, -1)
      (-1, 0, 0, 1)
        (0, 1, 0, -1)
        (0, -1, 0, 1)
    (-1, 0, 1, 0)
      (0, 1, -1, 0)
        (0, 1, 0, -1)
        (0, -1, 0, 1)
      (0, -1, 1, 0)


texts: How many operations of flipping all brackets on a substring of a string of brackets are needed to make the string 'correct'?

texts:
I call a string of brackets 'correct' if every opening bracket has a corresponding closing bracket somewhere after it and every closing bracket has a corresponding opening bracket somewhere before it. For example

  (())()((()()))

is a correct string and

  )()()(

is an incorrect string.

An operation consists of taking a contiguous subsequence of the input string and 'flipping' every bracket in that subsequence.

Given an arbitrary string of brackets (of even length), the task is to find the smallest number of such operations needed to change it to a 'correct' string of brackets.

Another way to look at this problem is to have a string of +1s and -1s, and to try to find the smallest number of operations (of multiplying every number on an interval by -1) needed to make every prefix of this string nonnegative and every suffix nonpositive.


texts: Reduction of flow-shop scheduling to a real-world computing problem

texts:
Consider the following well known flow-shop problem:

We are given a set of jobs $J=\{J_1,\ldots,J_n\}$ and a set of resources $R=\{R_1,\ldots,R_m\}$.  Each job $J_i$ consists of a set of operations $O^i=\{O_1^i,\ldots,O_p^i\}$.  Each operation $O_k^i$ requires exactly one resource $R_k^i \in R$ for a time fixed time $t_k^i$, and for each job, $J_i$ there is a set of precedence constraints (i.e., a partial order or directed graph) on the operations, $O_k^i \xrightarrow[\mathrm{before}]{} O_l^i$, stating that operation $O_k^i$ needs to finish before $O_l^i$ starts.

Is there any application of the above mentioned problem in computing (e.g. graph processing, image processing, distributed systems etc.)? Wikipedia tells me that "Flow shop scheduling may apply as well to production facilities as to computing designs" without providing a single example. I am looking for at least one example in computing in order to understand the significance of this problem in computer science. (I know the problem is NP-hard and that is enough to consider it as significant in computer science but I want to find a real world computing application which can be reduce to flow-shop problem).


texts: What is effect typing useful for when all global effects already have to be in the IO monad?

texts: This paper adds effect handlers to a number of languages, including Haskell - and also adds a form of effect typing to Haskell. But what's the point of the latter? I know that effect types can be used in a metaprogramming context (e.g. in a compiler) to prove the soundness of optimisations, but are there any uses of effect typing outside metaprogramming in Haskell?


texts: Error propagation when compiling a compiler

texts:
Just for curiosity, I recently heard that many compilers are written in its own language. For example, gcc is partially written in C. And old version of compiler is used to compile the new version of compiler.

Then I have a question, if there is a bug in the compiler, and you fix the bug in the source code and use the previous buggy compiler to compile a new compiler, how can you ensure that the bug in the new compiler is fixed?

Theoretically, if you have a very buggy old compiler, and now you have a new, bug-free version of the compiler source code, would the compiler converges to a bug-free compiler if you keep repeating compilation of the compiler starting from the old compiler?


texts:
I'm reviewing the definition of recursion and in my notes are two questions about a recursive problem. One question asks about the base case, the other one about the small version of the problem, I always get confused about which is which... can you help me to find a way to better understand these concepts?

The examples in the exercise are:

a function that determines if there is a "x" element in an array
a function that determines if the string is palindrome or not

for both:

Find the base case
Find the small version of the problem
(Implement the recursive solution)


texts: Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?

texts:
Hypercomputation is a "cheat" that extends the capability of a Turing machine or quantum computer or cellular automaton by adding extra abilities. A standard method is "Oracle machines", Turing machines with an extra black box device that can be queried and give an output that normally would be uncomputable. For example, a halting oracle would tell the machine a bit encoding whether an input program would ever terminate. Such "hypercomputation" machines can calculate various forms of uncomputable outputs.

My questions are:

Is hypercomputation compatible with our laws of physics?
What about other incomputable things like Russell's set (things which its result is not computable because it does not exist)? Or what about other uncomputable/illogical/impossible/non-existent/inconsistent things? Are there hypercomputational systems that could encode/compute them?

Thank you for your help


texts:
I am given a connected graph $G$ with some embedding. I want to find a non-deterministic algorithm running in $O(n)$ time to decide whether $G$ with that embedding is a plane graph (i.e, can be drawn without intersecting edges).
I know there exist algorithms that decide whether a graph is planar or not in time $O(n)$, but they are not given a fixed embedding, and only check whether there exists an embedding in which the graph is planar or not.
I also know that there are $O(n\log n)$ time algorithms that compute the intersection points of lines, but since my input is a graph with an embedding, it is less "general" than finding the intersection of a set of lines, so I suspect there might be a faster algorithm here.
I would be glad if you could refer me to some sources about this problem, and if a solution exists I would like to know more about it. Thanks in advance!


texts: Maximum matching using linear programming

texts:
In a bipartite graph $G = (V,E)$, there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to solve the following LP:

$$
\text{maximize}~~\sum_{e\in E} w_e x_e
\\
\text{subject to}~~\sum_{e\in E: v\in e}x_e=1\text{ for all }v\in V
\\
0\le x_{e}\le 1\text{ for }e\in E.
$$

If some value $x_e$ in the optimal solution is fractional, then there must be another fractional $x_{e'}$ near the same vertex (since the sum of all edges near each vertex is 1). By following these fractional edges, we eventually find a cycle of fractional edges. We can then move value along the edges in the cycle until at least one edge becomes integral (0 or 1).

A crucial aspect in this solution is that all such cycles are of even length, since the graph is bipartite. If the graph is not bipartite, then the above scheme does not work since we might have odd-length cycles.

QUESTION: Is there a similar algorithm for finding a maximum-cardinality matching, even in unweighted graphs, based on rounding a fractional solution to the above LP?

(I know that this problem can be solved by the blossom algorithm, but it is very complicated and I am hoping that the LP approach can yield a simpler algorithm).


texts: Intersection of Turing-recognizable language and regular language

texts:
True or false:
An intersection of a Turing-recognizable and a regular language is always Turing-decidable.

This was asked on a practice test and the answer is False. Why? I thought regular languages were a subset of decidable languages. So if you intersect regular and recognizable the result would also have to be a subset of decidable.

Is that not correct?


texts:
I want to show that there is a polynomial-time reduction from the standard $\text{Clique}$ problem to the $\text{N-Degree-Clique}$ problem, where:
$$ \text{N-Degree-Clique} = \{ \langle G, k\rangle: \text{$G$ has a clique of size $\geq k$,} \\ \text{and every vertex of $G$ has degree at least N} \}$$
I am not sure how to map the last condition and could use help figuring out a reduction.


texts:
How to do it?
I'm not asking the solution for the proof of why subset sum is NPC, but rather the opposite reduction


texts: Is it possible to always construct a hamiltonian path on a tournament graph by sorting?

texts:
Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order:

$\qquad \displaystyle a \leq b \iff (a,b) \in E \lor \left(\exists\, c \in V. a \leq c \land c \leq b\right)$

For context, this came from an observation that the inductive construction in the above page seems to be equivalent to insertion sort using the given order. Is it possible to use other sorting algorithms?


texts: Library for Maximum independent set on a sparse bipartite graph (from sparse matrix)

texts:
I am working with sparse matrices (not particularly huge, <100Mb) and I want to compute the largest independent set on the bipartite graph $(N,E)$ defined as follows: suppose the matrix is named $A$ and is of size $m \times n$.

$m+n$ nodes ($1,\dots,m$ for the rows, $m+1,\dots,m+n$ for the columns)
the edge $(i,j) \in E \iff a_{ij} \neq 0$

An independent set is then a subset of rows and columns such that they "do not intersect".

The graph is clearly bipartite (edges are from the set $\{1,\dots,m\}$ to the set $\{m+1,\dots,m+n\}$), and therefore the computation of the largest independent set is definitely simpler than the general case (as suggested also in this other question).

This computation is not entirely critical for my work (my thesis, actually) so I would like to use as much code from existing libraries as possible. I tried igraph, but they use a general algorithm for the largest independent set (which is terribly slow for even a matrix of 5MB), and I have yet to try and see if doing explicitly all the passages "Maximum Matching > Minimum vertex cover > maximum independent set" helps (it depends on their implementation).

The fact that I have a bipartite graph definitely helps from the theoretical point of view, so bigger instances are solvable, but yet I have to find a nice library which might work well with big, sparse, bipartite graphs.

Do you know any other existing libraries to do this kind of job?


texts: $1-2^{-23}$ and $2-2^{-22}$ both represents floating point representation or normalised representation.But are those two represent same value or both have different value? Is floating point representation same as IEEE representation??


texts: a program discovering himself how to solve propositional calculus

texts:
it is well-known that propositional logic problems such as

$$ (p\leftrightarrow q)  \lor r \quad\overset{?}{\vdash}\quad (((p\lor q)\to(p\land q)) \land \lnot r)\lor r$$

can be simply solved by evaluating the corresponding boolean functions for the $2^n$ possible values of the $n$ boolean variables (here $p,q,r$).

my question is then : instead of hand-writing such a propositional logic solver, couldn't we search for a program capable of generating such a solver ?

what would be then the minimal core / set of concepts and rules needed for a program being capable of ''discovering'' and ''solving'' the propositional calculus ?

is it a unsolvable artificial intelligence problem, or would it have some nice solutions, helpful for solving the more interesting higher order logics ?


texts: Is there a proof that "undetectable" malware cannot be written?

texts: In Fred Cohen's paper "Computer Viruses - Theory and Experiments", he proves that for the general case, classifying malware is an undecidable problem. I was wondering whether there might be a similarly well-known proof that an undetectable malware can or cannot be written.


texts:
From Sipser Gacs we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists t_1,\dots,t_{|r|}\forall r\in\{0,1\}^{|r|}\vee_{i\in\{1,\dots,|r|\}}M(x,r\oplus t_i)=1.$$
From Adleman we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists  r\in\{0,1\}^{|r|}M(x,r)=1.$$

Why is this just $BPP\subseteq P/Poly$ (looks like a derandomization to $BPP\subseteq NP$)? If Adleman's theorem just puts $BPP\subseteq P/Poly$ (because we need to find $r$) then why cannot I argue for similar reasons Sipser Gacs only puts $BPP\subseteq coNP/Poly$ (because we need to find $t_1,\dots,t_{|r|}$)?

What should Adleman's theorem have looked like if it indeed showed $BPP\subseteq NP$ and what should Sipser Gacs' theorem have looked like if it indeed showed $BPP\subseteq coNP/poly$?


texts: Modification of Nim Game Winning Strategy

texts:
Here is the variation:
We have some P piles of numbers,each having some pi numbers , and in each turn a player may choose a pile, and then a number from the chosen pile. All the numbers greater than equal to the chosen number are removed from the chosen pile.
We have to determine, if the player moving first has a winning strategy.

What I have done is, read about the NIM game and how we could generate a winning strategy. But this variation seems to have a dynamic rule set. Is this a standard type? If so, where can I read about this.? If not, how to approach this? Help in any direction will be appreciated.


texts: What does `Dv` mean in $F\star$ language?

texts:
In the $F\star$ tutorial it says

  Dv, the effect of a computation that may diverge;

what does diverge mean here? It's not explained and it confuses me.

I guess it means the type consists but the value varies, but if so why there isn't a non-diverge non-terminate effect?


texts: Contrast detection implementation for blur detection in microscopic image

texts:
I am currently doing a project where I have to detect if the the microscopic images given are blurry. I tried canny edge detection but they seem to perform not so good in detecting blur. I realised that I should rather look exactly for blur image detection. I found that modern cameras use contrast detection but I don't know how to implement it. Any ideas or resources to get it implemented. Any other approach which might help would also be great.

Thanks


texts: Non-deterministic 2-tape Turing Machine that recognizes palindromes in linear time

texts:
This question is taken from an exam of a Computer Theory Course.

  Describe how a NON-Deterministic Turing Machine with two tapes recognize in linear time palindrome strings with even length that have the form: $L=\{ww^R\mid w\in\{a,b\}^+\}$.

Tape 1: Read-Only & monodirectional
Tape 2: Read and Write, bidirectional

$w^R$ is the reverse of $w$.

My guess:

With determinism and  $L = \{{wcw^R | w \in \{a,b\}^+ \}}$ I copy the input from tape 1 onto tape 2, then I check if the first part of the tape is equals to second part using two markers, $X$ for $a$ and $Y$ for $b$ to keep track of the current iteration.

In every iteration of the algorithm I check if there is a corresponding $a$ (or $b$) in the second part of the tape, reading the tape backwards.

In the last iteration, if i read only $X$ or $Y$ i accept, otherwise reject.

With non-determinism: i need to guess where is the center of the tape. One of the configuration in the computation tree would be $wq_cw^R$ where $q_c$ identify the state representing the string's center. Here i can do the same verification for the deterministic version of the problem.


texts: Complexity classes pertaining to listing all solutions?

texts:
I was reading a question over at Stack Overflow asking whether it was NP-hard to list all simple cycles in a graph containing a particular node and it occurred to me that I couldn't think of any existing complexity class that was well-suited for talking about problems of the form "list all solutions to this problem." The class NP in some sense consists of problems that ask whether at least one solution exists, the class FNP asks to produce a single solution, and the class #P asks to count how many solutions there are, yet none of these deal with the complexity of exhaustively enumerating all possible solutions.

Is there a complexity class for describing problems that are of the form "given a polynomial-time computable predicate $P(x, y)$ and a string $x$, enumerate all $y$ for which $P(x, y)$ is true subject to [insert some appropriate complexity restrictions]?" I understand that it might be tricky to pin down the restrictions given that the number of solutions might be exponentially larger than the size of the input $x$, though that doesn't seem insurmountable.


texts:
What is the complexity class of an algorithm that runs in $n^{\mathcal{O}(\sqrt{n}log(n))}$ time?

As $n$ gets large $\sqrt{n}log(n)$ increases at a very slow rate. Does this mean that the algorithm has the same complexity as $n^{\mathcal{O}(1)}$, which would be in $P$?