texts:
I posted a question "Arbitrary Programs that halt" some days ago and now i think my doubt is a lot more clear.

I concluded that in any arbitrary program that halts, control flow operations, calculation operations ( 2+3 , "1 && 0", etc ) and memory assignment ( x:= "Hello" ) can be easily represented by Models of Computation such as Turing , RAM Machines, Lambda Calculus, etc.

But I/O operations such as reading input from keyboard/mouse/etc, writing output to monitor/speaker/network_device, don't really seem to have any relation to those models of computation, that is, i can't think of a way to simulate/emulate them there ( the only I/O operation that those models of computation could simulate is writing and reading from memory ) .    This reflects the fact that the programming languages were meant to access not only the CPU and the memory but the entire desktop PC ( including its additional I/O devices ).

At the same time, i've some people suggest that those I/O operations correspond to computations, in the Theory of Computation sense, and i'm thinking this is a problem because Turing-complete models of computation were mean't to possibly express ANY computation.

So, there are two possibilities  :
1 - Those I/O operations are not really computation and hence Turing-Complete models of computation are not required to express them, and also programming languages ( and our Desktops in general ) are modelling MORE than mere computation, they are modelling Computation + I/O.

2 - Those I/O operations are really "computation" and i simply don't know how to think of simulating them with Turing-Complete models of computation, that is, i can't seem a way to simulate the entire composition of a desktop PC ( CPU + memory + all external devices ) in those models of computation.

The first option seems more plausible to me, but i don't know.

What do you guys think about the relation between those I/O Operations and Computation ?


texts: I am struggling to understand why this property of asymptotic notation is true


texts: How does a remote connection knows it's endpoint inside a LAN?

texts:
I'm very curious about anything related to packet headers since im not well aware of how TCP/UDP protocols identify it's connection endpoint after a public IP is addressed. As for today I know the port will identify the process, but what happens when typically more than one computer is working over the same public IP and ports? No way more than one computer can listen to the same port? It is ultimately required to use more than one public address?

I guess i'm missing something very ridiculous here, and since its becoming a bit harder for me to find such details on internet I end up on here. Can someone clear me this in a nutshell?


texts: Negligible functions in definitions of statistical closeness and computational indistinguishability

texts:
Statistical closeness implies computational indistinguishability.

Is there any (simple) relationship between negligible function that is used in definition of statistical closeness and negligible function that is used in definition of computational indistinguishability?

Can we say anything about the negligible function used in computational indistinguishability if we know how the negligible function in definition of statistical closeness looks like?

What about the special case: negligible function in definition of statistical closeness is zero?

Definitions from Goldreich, Foundations of Cryptography:

Ensemble = sequence of random variables, $\{X_i\}_{i \in \mathbb{N}}$

Computational indistinguishability:

Two ensembles $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ are computationally indistinguishable if for every probabilistic polynomial-time algorithm $D$, every positive polynomial $p$ and all sufficiently large $n$'s,

$
  |P(D(X_n) = 1) - P(D(Y_n) = 1)| < \frac{1}{p(n)}.
$

(this definition actually says that $|P(D(X_n) = 1) - P(D(Y_n) = 1)|$ is negligible function in $n$)

Statistical closeness:

Ensembles $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ are statistically close if their statistical difference $\triangle(n)$ is negligible.

$
\triangle(n) = \frac{1}{2} \sum_a |P(X_n = a) - P(Y_n = a)|
$


texts: Can someone please help with the proof of this?

texts: Given an unambiguous context-free language L and an unambiguous regular language L (moreover, every regular language is unambiguous) such that L∩ R = ∅, then prove that L∪ R is also unambiguous.


texts: Is there any sort of formal definition of terms like 'data type', 'abstract data type', etc?

texts:
If not (because I assume not) is there some kind of reference or book that provides some theoretical foundation to these concepts? I've been learning about data structures and abstract data types for a while now but all these concepts seem very hazy and I would like some sort of rigorous grounding to stand on.

I hear type theory is used to found a lot of theoretical computer science (or all of it). So where could I read about type theory and how it is used to formalize CS?


texts: Difficulty in understanding this summations to analyze time complexity

texts:
I wanna know if what this link https://stackabuse.com/shell-sort-in-java/'s calculation of the complexity of shell sort is true.

Here's the shell sort algorithm:

void shellSort(int array[], int n){
    for (int gap = n/2; gap > 0; gap /= 2){
      for (int i = gap; i < n; i += 1) {
        int temp = array[i];
        int j;
        for (j = i; j >= gap && array[j - gap] > temp; j -= gap){
          array[j] = array[j - gap];
        }
        array[j] = temp;
      }
    }
}

Let me attach the site author's calculation using summations:

Where did he get the o(n log n) from? And why O(n^2)?


texts: Does there exist a type system for a non-let-polymorphic lambda calculus?

texts:
I'm wondering if there is a way to extend Hinley-Milner's type system to allow polymorphic types without the need of a let construct, by adding an intersection type (as Dan pointed out) that represents the possible types of a function type.

Say I have this expression:

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

While running the type inference algorithm, I'd normally, after looking at the expression $(x\ y)$, assign to $x$ some type $Y \rightarrow A$, where $Y$ is the type of $y$ and $A$ is whatever $x$ returns. Then, since $x$ also takes $(x\ y)$ which has the type $A$, I replace $Y$ with $A$, such that the type of $x$ becomes $A \rightarrow A$ and give to the whole thing the type $(A \rightarrow A) \rightarrow (A \rightarrow A)$.

But what if I, instead of replacing $Y$ with $A$ when I see $(x\ (x\ y))$, add a new type to $x$, say, $A \rightarrow B$, such that the final type is $((Y \rightarrow A) \wedge (A \rightarrow B)) \rightarrow (Y \rightarrow B)$, which is also a tautology and seems like a better representation of what the function does.

Now say I give to this abstraction the term $\lambda n.n$ like this:

$(\lambda x.\lambda y.(x\ (x\ y))\ \lambda n.n)$

Since $\lambda n.n$ has the type $N \rightarrow N$, I'd need to unify $N \rightarrow N$ with $((Y \rightarrow A) \wedge (A \rightarrow B))$. So I instantiate two copies of $N \rightarrow N$, say $N_1 \rightarrow N_1$ and $N_2 \rightarrow N_2$, and unify $N_1 \rightarrow N_1$ with $Y \rightarrow A$ and $N_2 \rightarrow N_2$ with $A \rightarrow B$. Because $A$ would be equal to $N_1$ on one side and equal to $N_2$ on the other side, $N_1$, $Y$, $A$ and $B$ are all equal to $N_2$, so the type $Y \rightarrow B$ becomes $N_2 \rightarrow N_2$, which is consistent with the expression you'd get after evaluating the lambda term.

With this type system I should be able to type things like this:

$(\lambda i.\lambda x.\lambda y.((i\ x)\ (i\ y))\ \lambda n.n)$

But these examples are simple, and it becomes a pain to type something like:

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

I'm having trouble trying to figure out what the actual rules of this system would be, like what would you do if you'd have to unify two intersection types (or whether that situation is even possible).

So my question is, am I moving towards a type system that already exists? If yes, which one? If not, is this because my type system wouldn't meet the requirements of a type system (such as being decidable)?


texts: Lambda calculus lists construction explanation

texts:
I have the following notes that introduce how lambda calculus handles lists. They go as follows:

A list is something we can match on and deconstruct if it is not
empty:
list match{
 case Nil => M
 case Cons(x,y) => N(x,y)
}

A list value is given by how it interacts with two terms M and N

(1) For starters I don't understand at all what is the role of M and N here. Then it continues:

We define it (a list) as a function that will take such M and N as
arguments
$Nil = \lambda mn.m$
$Cons(P,Q) = \lambda mn. n (P,Q)$

(2) Assuming I know how pairs and if constructs work in lambda calculus how can I come up with this expressions myself? I suppose that once this is clear I will be able to understand this sentence:

Cons is like a pair but takes m as argument, too, to fit along with
nil

Can you clarify points (1) and (2)?
Edit:
This are some further comments made in my notes that may make easier to understand what the intention of the writer is:
$Nil \  M \ N \implies M$
$Cons(P,Q) \ M \ (\lambda p. p._1) \implies \cdots \implies (P,Q)._1$


texts: Is the time complexity of this function O(n^3)? And O(n) for its memoized solution?

texts:
Given this naive recursive function:

def largest_tower(heights_and_widths, prev_height=1000, prev_width=1000):
    if not heights_and_widths:
        return 0

    results = {0}

    for i in range(len(heights_and_widths)):
        current_height, current_width = heights_and_widths[i]

        if current_height < prev_height and current_width < prev_width:
            subarray = heights_and_widths[:i] + heights_and_widths[i+1:]
            results.add(1 + largest_tower(subarray, current_height, current_width))

    return max(results)

At first sight, I would have said that the time complexity of this function is O(n^2). But, if I'm not wrong, explained in plain words would be: This function may call itself (n-1) + (n-2) + ... + 1 times, being that O(n^2), but a total of n times, so the actual time complexity is O(n^3). Am I right?

And for the memoized version:

def largest_tower_memoized(heights_and_widths, prev_height=1000, prev_width=1000, cache=None):
    if not heights_and_widths:
        return 0

    if cache is None:
        cache = {}

    results = {0}

    for i in range(len(heights_and_widths)):
        current_height, current_width = heights_and_widths[i]

        if current_height < prev_height and current_width < prev_width:
            subarray = tuple(heights_and_widths[:i] + heights_and_widths[i+1:])

            if (current_height, current_width) not in cache:
                cache[(current_height, current_width)] = largest_tower_memoized(
                    subarray, current_height, current_width, cache
                )
            results.add(1 + cache[(current_height, current_width)])

    return max(results)

I find this more complicated to explain. My intuition tells me that it's O(n), since we the recursion tree for each input is generated only once, but I'm not sure.


texts: Why doesn't descriptive complexity theory solve P = NP?

texts:
According to the Wikipedia page on Descriptive complexity theory:

  In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time.

  Existential second-order logic yields NP, as mentioned above.

If P = NP, wouldn't it be possible to convert any Existential second-order logic into a corresponding first-order logic with a least fixed point operator?  That would also imply a bijection between those sets (is there a bijection between existential second-order logic and first-order logic with a least fixed point operator?).

My understanding is first order logic cannot express second-order logic - why doesn't this prove P != NP?


texts: Combinatorial model for multiparty communication complexity

texts:
Brief introduction:

In two-party communication complexity, as presented by Yao in 1979, we model protocols as binary trees whose internal nodes are labeled by either Alice or Bob, and the leaves are labeled with possible  A node labeled by Alice is a step in the protocol in which she speaks. In these nodes that belongs to Alice, she computes a function which relies solely on her input $x$, and outputs a single bit which states whether to go left or right in the tree. Likewise for Bob, with his input $y$. The computation itself is a traversal over the protocol tree; since both Alice and Bob hear all the messages that are sent in the protocol, they both know the common state in which they stand, they can traverse the protocol tree together and reach the same leaf.

When discussing multiparty communication complexity, an immediate question that arises is the model of communication. In case of broadcast communication, commonly known as "the blackboard model", we can still formulate protocols as trees, and since everyone hears all of the communication, they can all traverse the protocol tree together. However, in case of point-to-point communication, commonly known as "the message passing model", such a model does not seem to work. In most papers, this model is presented as "in the message passing model, there are $\ell$ players that can send each other messages over private channels between each two players", and that's it.

The question:

Do you know of any simple combinatorial way of modeling such protocols? Or can you think of such a way?

Thanks in advance.


texts:
Given this algorithm:

int foo(int num) {
    if (num == 0){
        return 0;
    } else {
        return 1 + foo(num/10);
    }
}

Me and my friend are debating how you should treat "N" as the size of the input.

If I'm considering N to be the number of digits: then my analysis will say O(n)

However, if I'm considering N to be the actual value of the input to the function I will get a different runtime representation and different analysis with the conclusion of O(log n) (base 10)

Me and my friend cannot understand why the second approach is wrong, so far we got explanations like : "The algorithm is cutting the number digit by digit so your N is the number of decimal digits of the number"

However, log (base 10) of the actual value will give me pretty much the same result.

Why is the second approach is wrong ?


texts: #3-Coloring Problem for Tree with Some Pre-Colored Nodes

texts: I have a undirected tree and three colors to choose from. Some nodes are already colored; these nodes and their colors are given. What is an efficient algorithm to find the number of ways to color the rest of the nodes such that no two adjacent nodes are the same color?


texts:
Given a set of permutations $P$ of size $n$, is it possible to create a data structure that, given a sequence $s$, returns $p \cdot s$ where $p \in P$ such that $p \cdot s$ is canonical wrt. $\{\,q \cdot s \mid q \in P \,\}$ faster than $O(n)$ time?

By canonical, I mean for example such that $p \cdot s$ is lexicographically minimal, but any kind of canonical will do.

This is easy to do in $O(n)$ time. You just try every single permutation and pick the canonical one (eg. minimum), but is there a faster way?

Example

For lexicographically minimal canonicalization, if $P=\{ (1,2,3,4),(4,3,2,1),(2,3) \}$ and $v=(0,5,1,0)$, then the result would be $(0,1,5,0)$. This is the application of either the permutation $(4,3,2,1)$ or $(2,3)$, as they are identical in this case.


texts: How to get expected running time of hash table?

texts:
If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in the hash table and use a hash function which assumes simple uniform hashing assumption. Then before every insert you just check all elements in the chain. This makes less collisions and makes the average length of a chain $\alpha = \frac{n}{m} = \frac{n}{1000}$.

I am trying to get the expected running time of this, but from what I understand, you are doing an insert operation up to $n$ times. The average running time of a search for a linked list is $\Theta(1+\alpha)$. Doesn't this make the expected running time $O(n+n\alpha) = O(n+\frac{n^2}{1000}) = O(n^2)$? This seems too much for an expected running time. Am I making a mistake here?


texts:
I am working with this problem:

What is the asymptotic running time of the following piece of code?

if (N < 1000)
   for (int i = 0; i < N*N*N; i = i+1) A[i] = j;
else if (N < 10000)
   for (int i = 0; i < N; i = i+1) A[i] = j;
else
  for (int i = 0; i < N*N; i = i+1) A[i] = i;

Where the possible answers are:

A) linear in N
B) linearithmic in N
C) cubic N
D) quadratic in N

I am unsure how to calculate it, but when I look at the code I think A and B is not the right answer, because of the for-loops multiply with the variable x-times. If possible, could someone also explain what "Asymptotic time" means?


texts: Is finding all cycles in a graph using some version of Johnson's algorithm (code provided) really polynomial (benchmark provided)?

texts:
This is the algorithm I'm using:
https://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs/14115627#14115627

Specifically C#, but the linked thread has numerous languages.

Worst case time complexity should be O(|V|^{2}\log |V|+|V||E|)}
https://en.wikipedia.org/wiki/Johnson%27s_algorithm

My findings running benchmarks using the first algorithm linked:

[polygons (each 3 vertices and 3 edges): milliseconds]

10: 332 ms (~30 vertices, 30 edges)
11: 789 ms
12: 2344 ms
13: 7524 ms
14: 16788 ms
15: 54182 ms (~45 vertices, 45 edges)

That's exponential growth!

My only question:
Is this a polynomial time algorithm that I'm using to find all cycles in a graph or not?

Thanks :)


texts: Fastest way to find natural solutions to Linear equation

texts:
$$
a_i * x_i + b_i * x_j = N
$$

$\text{given } a_i, b_i, N \in \mathbb{N}$

i want to find a solution where $x_i, x_j \in \mathbb{N}$ or output if there exists none.

What is the fastest way to calculate this?


texts: Thought process to solve tree based Dynamic Programming problems

texts:
I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems and I was hoping somebody could please explain their thought process.

I will talk about my thought process behind array based problems and then explain my troubles with tree based DP problems.

My thought process for array problems

The way I think about DP in array based problems is as follows. Let us consider a problem like Minimum Path Sum. Here the objective is to get from the top left to bottom right positions in a matrix such that we minimize the cost of the path. We can only move left and right.

The way I would approach problems like this is as follows:

First I would construct a recurrence. In this case the recurrence is as follows

The recurrence is:

f(i, j) = a[i][j] // if i == m and j == n
f(i, j) = a[i][j] + f(i, j+1) // if i == m
f(i, j) = a[i][j] + f(i+1, j) // if j == n
f(i, j) = a[i][j] + Math.min( f(i, j+1), f(i+1, j) ) // Otherwise

Next I look at the equations which tells me the problem can be solved using DP as there are overlapping subproblems in f(i+1, j) and f(i, j+1). There is also an optimal substructure.
I can also tell the time/space complexity just by looking at the recurrence.

Because we must compute all states which is all (i,j) pairs and because time per state is O(1) (adding a[i][j] to result) the time complexity is O(n^2).
Looking at the recurrence, i depends only on i+1 and not on i+2, i+3 ... similarly j depends only on j+1 and not on j+2, j+3... so we can get away with using only 1 extra row (either i+1 or j+1) instead of the entire matrix so space complexity is O(n).

Hence I would come up with a n^2 time and n space solution. I can do this without any problems.

My thought process for tree problems

However I am having a hard time applying the same thought process to tree based DP problems. As an example let us consider the problem Diameter of Binary Tree where the objective is to find the longest path between any 2 nodes in the tree.

I can come up with a recurrence for this problem which is as follows:

f(n) = 0 // if n == null
f(n) = max( 1+height(n.left) + height(n.right),         // longest path passing through root
            f(n.left),                                  // longest path in left subtree
            f(n.right) )                                // longest path in right subtree

Because f(n.left) for example is computed by doing 1+height(n.left.left) + height(n.left.right) I can tell that DP must be used.

So my approach would be to create a cache of size 'n' that stores all the heights of the nodes. So the space complexity would be O(n).

However the optimal solution of this problem has a space complexity of O(1) and I am having a hard time figuring that out just by looking at the recurrence. How does the recurrence tell you that space complexity can be reduced and that O(1) space is enough and O(n) is not needed? How do you know what value(s) to store in this case? In array based problems I can get the answers to both these questions just by looking at the recurrence but for tree based dp it is not so obvious to me.

My questions:

What can you tell about this problem just by looking at the recurrence for the tree problem? Putting aside my own thought process, if I gave you this recurrence and nothing else what conclusions would you reach and how would you write the program? I am curious about your thought process.
For array based problems I can tell just by looking at the recurrence both how much space I needed to solve the problem AND what exactly I needed to store (I need to store values of row i+1 in min path sum and nothing else). How can I do the same for the tree problem?

Thanks.


texts: Can properties such as memory usage of a function be expressed in a dependently typed language?

texts: Suppose one wants to reason about properties of code beyond things like totality and functional purity - one also cares about the memory consumption, or algorithmic complexity of a function. Can this be done through dependent typing and effects systems?


texts: Number of literals in the given boolean expression

texts:
Count the number of literals in the following expression :

F = AB' + BC' + CD' + DE'

According to me, the answer should be 8. But my solution suggests that the answer should be 6. Can anyone help me out. What am I doing wrong?

Thanks in advance!


texts: Multiplication function BDD size lower bounds

texts:
Randal Bryant developed an exponential size lower bound for any BDD encoding the middle bit output of the multiplication function, regardless of variable permutation.

But at the same time the multiplication function is decidable in logarithmic space. Of course related to P versus NP, the lower bounds complexity of its inverse function is currently unknown. Having an efficient BDD encoding for multiplication also provides a mechanism for efficient factoring, so I understand that this would seem implausible.

However, if a function belongs to L (such as multiplication or so I think), it most certainly belongs to L/Poly which is (to my understanding) the class of polynomial sized BDDs.

From what I can discern, Bryant's proof relies on communication complexity rather than crypto-hardness assumptions or building upon mainstream conjecture. So what's going on here that seems a blatant contradiction in known lower bounds?

For some related background see this post:
https://cstheory.stackexchange.com/questions/3462/most-significant-bit-of-integer-multiplication-and-binary-decision-diagrams


texts: Conceptually, I know that reducing a problem $Y$ that's NP-complete to a problem $X$ implies that $X$ is at least as hard as $Y$, implying $X$ is also NP-complete. So if any NPC problem, say $Z$, can be solved in polynomial time, then that implies $P = NP$, since any other NP-complete problem can be reduced to $Z$ in polynomial time, and then solved in polynomial time. But what does it mean to reduce a problem in $P$ to a problem in $NP$? I feel like this is self-evident (problems in P are no harder than problems in $NP$), but is there any example that can make this clearer?


texts:
I need to prove a bisimulation relation on $CA_{\tau}(N)$ (communication algebra with tau-steps) and names $N$.

It need to prove that $p!d.x||p?d.y$ is bisimular with $p!d.(x||p?d.y)+p?d.(p!d.x||y)$ by finding a suitable bisimulation relation $R$.

I was thinking of $R=\{(x,x) \mid x \text{ is a reachable state} \} \cup \{(p!d.(x||p?d.y)+p?d.(p!d.x||y) \mid x\text{ and }y \text{ are reachable states} \}$.

Is this a suitable relation? How do I prove that.

Note: the definition of bisimularity in this book is:
$x$ is bisimilar with $y$ when there exists and relation $R$ on automata $M$ and $M'$ with sets of states $S$, $S'$ such that:

$R$ relates the reachable states
$R$ relates the initial states
Whenever $sRs'$ and $s$ has an $a$ step to $t$ for some $a$ in the alphabet, then there are states $s''$ and $t'$ in $S'$ such that $s'$ has an $\epsilon$ path to $s''$ and $s''$ has an $a$ step to $t'$ and both $sRs''$ and $tRt'$.
Whenever $sRs'$ and $s'$ has an $a$ step to $t'$, then there are states $s''$ and $t$ in $S$ such that $s$ has an $\epsilon$ path to $s''$ and $s''$ has an $a$ step to $t$ and both $s''Rs'$ and $tRt'$.
Whenever $sRs'$ and $s$ has an $\tau$ step to $t$, then there are states $s''$ and $t'$ in $S'$ such that $s'$ has an $\epsilon$ path to $s''$ and either:

$s''=t'$ or
$s''$ has an $\tau$ step to $t'$ and both $sRs'$ and $tRt'$

Same as $5$, but then from $M'$ to $M$.
Whenever $sRs'$ and $s'$ terminates, then there is a state $s''$ in $S'$ such that $s'$ has an $\epsilon$ path to $s''$ and $s''$ terminates and $sRs''$.
Same as 7, but then from $M'$ to $M$.

How can I prove such relation?


texts: Relational algebra for multiple legs of a flight

texts:
I'm trying to write the relational algebra for a problem related to this schema:

I want to do the following: For each flight list the departure airport code for the first leg of the flight and the arrival airport code for the third leg.

I know how to do this for the individual parts, but I'm not sure how to select from multiple different instances of leg_instance.

This is what I have to start:

π airport.airport_code (flight) ⋈ flight.flight_number = leg_instance.flight_number (leg_instance) σ leg_instance.leg_number = 1


texts: finite automata that accepts integers divided by 3?

texts:
I have found in a book the example of how to make a FA that accepts those numbers that are divisible by 3, that means that n mod 3=0. In the example the author used the binary representation of the number to be evaluated. The resulting automata is:

The states represent the probable remainders, that could be 0, 1 or 2. Some additional explanation is in the following part:

I have tried the following examples to test this automata:

If I try to do 6 mod 3 that will result in 0, so I will go from the
initial state (upper part of the figure) to the acceptance state,
that is because the modulus is 0.
If I try 5 mod 3 or 101 mod 11 that    would be 2, which in binary is 10. If I want to apply again 2 mod 3. I    will end up again with 2 and not reaching an acceptance state. From    the upper part I
followed the path 1--state 1--0--state 2. What    happens there? it
just stays in that state 2?

I just do not have a clear picture of how to test this FA for example with an input of 81 mod 3, does it make partial divisions? When I try to follow it I end up in an acceptance state even before finishing to evaluate the remainder.

Any help?


texts: What did Turing's mysterious small programme on the Manchester computer calculate?

texts:
I am reading Turing's "Computing machinery and intelligence" paper (https://www.csee.umbc.edu/courses/471/papers/turing.pdf) and found a fragment in which he says:

  I have set up on the Manchester computer a small programme using only 1,000 units of storage, whereby the machine supplied with one sixteen-figure number replies with another within two seconds. I would defy anyone to learn from these replies sufficient about the programme to be able to predict any replies
  to untried values.

It looks like a machine learning problem to me :) but putting my interest on AI aside, my question is the following:

Does anyone know what this program was doing?

I am very curious.

PS: By the length of the input and output, I suspect it was an encryption algorithm, but I would appreciate any clue to the actual program.


texts: I do not understand the following options in windows. Could any one explain


texts:
An apology might be in due for asking another question about prerequisites, but I was confused about the starting points.
I have come across various terms such as "Modal Logic", "Temporal logic", "First -order Logic", "Second order Logic" and "Higher order logic".

What exactly does "Logic" mean in this context? How do we rigorously define the word "Logic"?

After going through the beginning pages of few books I can roughly conclude that
a "Logic is a way to decide what follows from what and is significant in designing programming languages as it dictates and facilitates designing of programs to automatically reason and understand programs.
I want to understand about the second point in a bit elaborated manner.

Now coming to these logics.

Are all these logics, "temporal Logic", "Modal Logic", "First order Logic", "Higher order Logic" independent of each other or we need to understand few of these logic to understand a few others in this group? In a nutshell, what will be the prerequisites for them? (It will be great if I can get suggestions on some materials also.)

P.S : Thanks a ton for your kindness


texts: Dynamic Programming vs Greedy - coin change problem

texts:
This is a fairly common problem:

Given coins of integer denominations $v_1 < v_2< ... < v_n$, make change for an amount A using as few coins as possible.

Given an input of powers of $p$,

$V = [1, 3, 9, 27]$

How would a dynamic programming vs greedy approach differ in this algorithm?  I don't have a good general idea of how these approaches would differ.


texts:
Given a finite set $\Omega$, I have the following problem. Say there is a list of forbidden subsequences $F \subset \Omega \cup \Omega^2 \cup \Omega^3 \dots \Omega^\infty$, while we do not know the contents of list before hand, we can make a query about any sequence $S \in \Omega^i$ to see if $\exists f \in F, f \subseteq S$. (here $f \subseteq S$ means that $f$ is an uninterrupted "substring" of $S$) I want to construct a sequence $S \in \Omega^n$ such that $f \not \subseteq S, \forall f \in F$.

The approach I thought would be best is to use dynamic programming. We iteratively construct valid sets $V_k := \{S \in \Omega_k: f \not \subset S ,\forall f \in F, |f|< k\}$, by requiring each subsequence of $s \in V_1 \cup \dots V_{k-1}, \forall s \subsetneq S$, and then remove all $S \in F$ with queries. My question is, what's the most efficient way to construct $V_k$? One simple way would be to take $V_{k-1}$ and then try adding each element in $\Omega$ at the end, and then do some extra queries, but is there some better way?

Additionally, are there elegant ways to use incomplete valid sets $I_k \subseteq V_k$, where if $I_{k+1} := \{S \in \Omega^{k+1} \setminus F: s \in I^1 \cup \dots I^k, \forall s \subsetneq S\}$ is empty, we can try to retroactively expand everything without mostly starting from scratch?


texts: Token Scanner for programming Language(Lexical Analysis)

texts:
This DFA is a token scanner for a programming language.I would like to add keywords of the programming language(if,else,end ... etc) in the DFA so the lexical analyzer can recognize them.

The Question is : Do i have to convert the entire given DFA to an ε-NFA(which will result in more states),add the keywords(with ε transitions too)and then convert back to a DFA or i just have to add the keywords so that the DFA becomes an NFA and then convert back to a DFA


texts:
I want to prove the non deterministic space hierarchy theorem.

Let $f(n),g(n)\geq\log n$ be space constructible functions such that $f(n)=o(g(n))$, Prove:

$$NSPACE(f(n))\subsetneq NSPACE(g(n))$$

I feel that the standard way of constructing a TM that takes as an input a TM and simulates the machine on itself, then flipping the output won't work because the input is a nondetrministic TM maybe. Can someone suggest a hint?


texts: How can I prove the correctness of this exponentiation algorithm using induction?

texts:
I have the following algorithm. How could I prove it using induction that for every $n\ge 0$, Exp(n)${}= 2 ^ n$?
Exp(n)
    If n = 0
        Return 1

    If n is even
        temp = Exp(n/2)
        Return temp × temp
    Else
        temp = Exp((n−1)/2)
        Return temp × temp × 2


texts: Fast software pipelining for stream processing

texts:
I have a pipelined stream processing situation, where a number of streams is linked in the computational process S0 -> S1 -> S2 -> .... You can understand "stream" as a list of numbers.
In this process, S0 is initially given in totality. S1 is a mapped result from S0 according to function f; S2 is the result from S1 by the same f, so on and so on. f(S) works by traversing stream S linearly and produces the resulting stream as it goes. Hence, f can work on a stream "partially": that is, for example, we don't need the totality of stream S1 in order to begin producing S2. The processing S0->S1 can occur concurrently with S1->S2 in a pipelined fashion.
I attempted implementing this pipeline using C. In my code, I use an atomic variable to synchronize progress between each pipeline stage $S_i\quad\overrightarrow{\small f_i}\quad S_{i+1}$: basically, thread $f_i$ constantly polls progress from the previous pipeline $f_{i-1}$ to see if new tokens are written into $S_i$. If so, it continues its own work. Otherwise, it spins and waits. Of course, this assumes each $f_i$ is responsible for reporting its progress to $f_{i+1}$. It turns out that this synchronization is too costly. I wasn't able to gain any speedup using multiple threads. In fact, it makes the code much slower than a single-threaded implementation.
My question is, what is a better approach to implement this construction in order to actually take advantage of multi-threading? This seems to be very hard because the $f$ in my scenario is computational-bound. It seems to me highly unlikely to extract parallel performance unless there is a very low-cost synchronization scheme. Thanks in advance for any comments and advice.


texts: The set of words accepted by TMs simultaneously is finite is non semi-decidable

texts:
Consider $L = \{(M_1,M_2):\text{the set of words accepted by both TM at the same time is finite}\}$. I want to determine if this language is decidable, semi-decidable or not semi-decidable.

My thoughts

My intuition tells me this is a nonRE language. Before, I showed that the same language considering the condition "there exists a word accepted by both" is semi-decidable. However, the condition of being finite is too much since one should check all the words accepted by the machine (in order to show that it is in fact finite).

Therefore, I think I have to try reductions of nonRE languages. I tried with $L_e$ machines that produce the empty set, but this condition doesn't seem to go well with the non-finiteness I need at some point of the implications.

Maybe you have some suggestions.


texts: Product of a Transition System and a Finite Automaton

texts:
Dealing with a question that asks me to compute the product of the following transition system and finite automaton.
Compute the product between the transition system TS and the finite-word automaton A depicted below.

Can't seem to find a good example on how to do this so I sort of just freestyled my answer. The best I found was in Principles of Model Checking but the book didn't really explain how the product was derived (it just provided a TS, FA and product), so I had to "guess" the logic.
Can anybody have a quick look at my solution and see if there are there any obvious mistakes I have made?

Also I can't figure out whether or not I should indicate any terminal states. I know that a TS doesn't have any terminal states, but an FA can - so what about the product?


texts: Influence of the dimension of cellular automata on complexity classes

texts:
Let's take as an example the 3d → 2d reduction: What's the cost of simulating a 3d cellular automaton by a 2d cellular automaton?

Here is a bunch of more specific questions:

What kind of algorithms will have their time complexity changed, by how much?
What would be the basic idea for the encoding; how is a 3d grid efficiently (or not efficiently…) mapped to a 2d grid? (The challenge seems to achieve communication between two cells that where originally neighbors on the 3d grid, but are not neighbors anymore on the 2d grid).
In particular, I'm interested in the complexity drift for exponential complexity algorithms (which I guess remains exponential whatever the dimension, is it the case?)

Note: I'm not interested in low complexity classes for which the chosen I/O method has an influence on complexities. (Maybe the best is to assume that the I/O method is dimensionless: done locally on one specific cell during a variable amount of time steps.)

Some context: I'm interested in parallel local graph rewriting, but those graphs are closer to 3d (or maybe ωd…) grids than to 2d grids, I'd like to know what to expect of a hardware implementation on a 2-dimentional silicon chip.


texts: An algorithm to generate all connectible pair combinations

texts:
In this thread I am seeking for an advice or a starting point on how to solve the following riddle. I need to come up with an algorithm which will generate all possible combinations, but I don't know where to start. In this example let's assume that we have 3 value pairs

1 2

2 3

3 1

The aim of a riddle is to make as much UNIQUE pair connections as possible. So the first KeyValuePair can connect on value 2 of second KeyValuePair, whereas second KeyValuePair can connect on number 3 of third KeyValuePair. Start and End key can not be the same. Here is a graphical representation of the expected result:

Valid combinations:

1 2  (1 - 2 connection)

2 3  (2 - 3 connection)

3 1  (3 - 1 connection)

1 2, 2 3 (1 - 3 connection)

1 2, 3 1 (2 - 3 connection)

2 3, 3 1 (2 - 1 connection)

Invalid combinations:

3 1, 1 2 (3 - 2 connection, duplicate)

2 3, 1 2 (3 - 1 connection, duplicate)

3 1, 2 3 (1 - 2 connection, duplicate)

1 2, 2 3, 3 1 (connection: 1 - 1, not unique, 'Start' and 'End' key can not be the same)

I hope I did not miss anything :). A graphical representation of joining would be:

Pair 4 1 was added for the sake of demonstration. In a real world application I expect there to be 100+ pairs. Therefore an algorithm must be efficient. Also (sorry if this is too much) I will need to make sure that there are no more than 3 pairs in a chain (therefore above image is not entirely correct)! But this requirement can be ignored right now, for the sake of simplicity. How to design an algorithm like this?

EDIT:
Based on comment replies I think I need to provide additional explanation of the real use-case for this algorithm. In reality there will be currencies instead of numbers. So EUR/USD is 1 - 2, USD/RUR is 2 - 3, RUR/EUR 3 - 1, in that case (EUR/USD - USD/RUR) is also 3 - 1, but fundamentally it is different kind of conversion! What we are searching here is basically how every currency can be converted to any other currency. For that same reason EUR/USD - USD-RUR - RUR/EUR (= EUR/EUR) is not a valid case. Hope that explains it a bit better.


texts:
The $3-SAT$ problem is known to be NP-complete problem. Which means that (as far as I understand), unless $P \neq NP$, for every algorithm $A$ which decides $3-SAT$, $A$ runs in super polynomial time (I know that this is not well defined). A stronger assumption is the "Strong Exponential Time Hypothesis " which states that every algorithm has to run in worst case exponential time.
Does that mean, for example, that every algorithm $A$ (here I refer to a "real" or practical implementation, such as Glucoses, DPLL, Z3, etc.), has an instance of size, say 200, which $A$ will not be able to solve in a reasonable time? I see many sat solvers solving formulas with millions of variables in very short time; and I am aware of subsets of $3-SAT$ which are easy, such as Horn clauses, or a random instance with a known density - but it seems that these solvers work amazingly fast without any assumptions on the input.
I have searched for Sat benchmarks, or instances which should be hard, but when running them on a modern sat solver, it doesn't seem to be a problem.
It is known that complexity assumptions (or claims) are about the asymptotic behavior, my question is: do we know for which $n_0$ these assumptions "kick in" in the case of $3-SAT$? Can we generate, or at least be confident of the existence of a relatively small formula ($< 200$), such that every algorithm requires $\sim2^{200}$ operations?


texts: IEEE largest number for any machine representation

texts:
If we consider a machine that uses 64 bits to represent a number.

If 1 bit is used for sign, "x" bits to represent mantissa and (63-x) to store the (biased) exponent in a manner similar to the IEEE representation.

I'm using this question to check my knowledge of IEEE. Can we say the largest positive number using this machine is:   $\left ( 63-x \right )* 2^{2^{x}-1}$


texts: English Translation of "Connectivity of Probabilistic Networks"

texts:
A seminal paper in network reliability is "Connectivity of Probabilistic Networks" by Kel'mans, with a link here.

However, the linked PDF file is in Russian. Is there an English translation available online? The version journal/year (Automation and Remote Control, 1967, 444–460) listed there does not seem to be available online.


texts:
If you have a language $L_1 = \{ w | w \in \{a,b\}^* \}$. Then does the language $L_1^R$ (the reversal of $L_1$) have the exact same elements as the language $L_1$?

My Logic: Since $L_1$ can contain a string as well as the reversal of the string (ex. $L_1 = \{ababba, abbaba\}$), then $L_1^R$, over the same alphabet, can contain the same strings as what $L_1$ has (ex. $L_1^R = \{abbaba, ababba\}$ which is equivalent to $L_1$)?

Am I looking at this correctly?


texts: Greedy Proof: For coin denomination systems, faster proof to ensure greedy solution yields the optimal solution

texts:
I have reasons to believe that there is a faster way to confirm, that for coin denomination systems if the greedy solution yields the optimal solution or not.
I believe that if you check that for all values
from the Largest denomination to 2nd largest denomination, the greedy solution is the optimal solution, then for that custom coin denomination system, the greedy solution will always yield the optimal solution.
For example.
1,5,7 <- For this greedy solution != optimal always
as for values n = [7,5+7] ; n = [7,12], for n = 10, optimal (5,5) != greedy (7,1,1,1)
1,7,13,19,61 <- Greedy Solution == optimal always
as for values n = [61, 61 + 19] ; n = [61, 81] greedy is always optimal
1,7,14,20,61 <- greedy solution != optimal always
as for values n = [61, 61+20] ; n = [61, 81] for n = 80, optimal (20,20,20,20) != greedy (61,14,1,1,1,1,1,1)
I was wondering if this has already been discovered or not?
If so, is there a proof that I can be pointed to?
If not, can I know how should I go about proving this point?


texts: Use the pumping lemma to show it's not regular

texts:
I just learned pumping lemma this week and got confused on this question.

B={$a^{fn}$ | $f_n$ is a Fibonacci number} for $a \in Σ$.

Hint: the sequence of Fibonacci numbers get increasingly further apart.

I am trying to prove this is not regular using pumping lemma, but 'Fibonacci numbers get increasingly further apart' seems really tricky when I try to pump up to prove it's not $\notin$ B.


texts: Growth of non-terminating beta reductions in lambda calculus

texts:
There are some terms in lambda calculus that don't really have a normal term. My question is for a term like the following:

$$T \overset{def}{=} \lambda f. (\lambda x. \; f \; (f \; (f \; x)))$$

$T$ takes a function as its argument and transforms the function space by applying it three times. If I apply $T$ to itself, I will be initially left with
$$\lambda f. (\lambda x. \; f \; (f \; (f \; x)))\; \lambda f. (\lambda x. \; f \; (f \; (f \; x)))\; \lambda f. (\lambda x. \; f \; (f \; (f \; x)))$$

But I can continue to do this an infinite amount of times. After my first reduction, I am left with 3 terms.  So how do we define the growth of the function per reduction? Do we say that my next reduction will leave me with 9 terms, or 27? Or 81?

Also, how do we define the nature of the expression? Does it have a normal form?


texts: Modeling a sequential circuit as a transition system

texts:
I was asked to model the following sequential circuits C1, C2 as transition systems (i.e. identify the output y function and register functions r1, r2, r3)

For C2 there appears to be not input x and only output y with a register R3. I assumed that there would be two possible states R3 = 0, R3 = 1 and then Y2 = !R3. But then what is the register function for R3?

For C1 I really had no idea how approach the problem as it was just an intimidating maze and while I thought it may be possible to break the circuit up and try find the functions that way, I wasn't sure.
I would like to know how I can find the output and register functions of these circuits


texts: Prove NP-completeness for union of NP-complete language and language in P

texts:
Given disjoint languages $X$ and $Y$, where $X$ is NP-complete and $Y\in P$ , how do I prove that $X\cup Y$ is NP-complete?

My idea is to prove that $(X\cup Y)\in NP$ and then prove that $X\cup Y$ is NP-hard:

I can prove $(X\cup Y)\in NP$ by saying that since both are in NP, they each have polytime verifiers. Thus we can have a polytime verifier that on any input will use these verifiers and accept if any accept, reject otherwise.

I am stuck on the part of proving NP-hardness. The idea of arbitrary languages is throwing me off; I am trying to reduce a NP-complete problem (SAT for example) to $X\cup Y$ and using the fact that $X$ has some method to reduce to it already but I am lost as for what to do with $Y$. I am thinking that given an input for SAT, I need to somehow change the input so that I can relate acceptance in $X\cup Y$ to acceptance in SAT; same for rejection.

Any guidance would be appreciated; thanks!


texts: How to prove optimal substructure for Lecture Hall assignment problem?

texts:
In CLRS, an approach has been given to prove the optimal substructure and the correctness of the greedy algorithm for the activity selection problem. In the Lecture Hall assignment problem, we sort the classes according to their starting times and assign them lecture halls accordingly, choosing a new lecture hall if the timings of the class conflict with all the existing lecture halls. Is there a way to prove the optimal substructure in this problem? Why do we only sort the lectures according to their starting times and not according to their finishing times?
How can we prove that there is always an optimal solution which makes the greedy choice?


texts:
From the wiki https://en.wikipedia.org/wiki/Paxos_(computer_science)

If a Proposer receives enough Promises from a Quorum of Acceptors, it needs to set a value v to its proposal. If any Acceptors had previously accepted any proposal, then they'll have sent their values to the Proposer, who now must set the value of its proposal, v, to the value associated with the highest proposal number reported by the Acceptors, let's call it z. If none of the Acceptors had accepted a proposal up to this point, then the Proposer may choose the value it originally wanted to propose, say x.
The Proposer sends an Accept message, (n, v), to a Quorum of Acceptors with the chosen value for its proposal, v, and the proposal number n (which is the same as the number contained in the Prepare message previously sent to the Acceptors). So, the Accept message is either (n, v=z) or, in case none of the Acceptors previously accepted a value, (n, v=x).

Question. If a Proposer received from an Acceptor number higher from Proposer number (Proposer sent number=2, but received from Acceptor number=3). Current a Proposer value is not outdated? (because number=3 already exist in Acceptors). Why a Proposer must send value z (value z already exist into Acceptors)?


texts: Direction of restriction for NP hard proves

texts:
I have a very silly question, as I am reading through all the proofs showing a problem is NP hard, one of the techniques is by showing an already-proven NP complete problem is a special case for that problem.

I am wondering shouldn't that be another way around? I mean if you show your problem is a special case of a NP-complete problem, then you showed it is NP complete as well? I know this logic is wrong but why?

What is the advantage and disadvantage of this technique.

Comment: this question actually contents the answer for why we need to reduce a problem to a NP hard problem to prove its NP hardness.


texts: How to remove empty strings a.k.a (lambda, epsilon) from a LR(0) grammar

texts:
Say I have the following grammar:

E  -> TE'
E' -> +TE'| -TE' | λ
T  -> (E) |  id

I need to build the finite state machine with the LR(0) items,

But I know in order to do this I have to remove the λ.

How to I accomplish this ?

Also, after I have the SLR(1) table, how to  I prove is valid ?

Thanks, I'm studying for an exam, and I'm stuck here :(


texts: Where's the flaw in my algorithm? (Linear program to solve NP-hard problem)

texts:
The problem (copy-pasted from this question on cs.stackexchange):

Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?

My algorithm:
We first add weights to the edges:

If the edge goes into a red vertex, we let its weight be -1.
If the edge goes into a blue vertex, we let its weight be 1.
Any edge going into $t$ has weight 0.

This way, any path from $s$ to $t$ with negative weight is a solution.

We now formulate a linear program, which finds the path with lowest weight from all paths with length $\le c$ (i.e. it only looks at paths with $\le c$ edges ):

Minimize the function:
$$ \sum_{e\in E} c_e\cdot x_e $$

Under the constraints:
$$
\forall v\in V-\{s,t\}: \sum_{e\in in(v)}x_e -\sum_{e\in out(v)} x_e = 0
\\
\sum_{e\in out(s)} x_e = 1
\\
\sum_{e\in in(t)} x_e = 1
\\
\sum_{e\in in(s)} x_e = 0
\\
\sum_{e\in out(t)} x_e = 0
\\
\sum_{e\in E} x_e \le c
\\
\forall e\in E: x_e \ge 0
$$

Here $c_e$ are the weights of the edges, $in(v)$ are all edges going into $v$, and $out(v)$ are all edges starting in $v$.

This linear program is, except for the constraint $\sum_{e\in E} x_e \le c$, identical to the one which I asked about in my previous question, and in which it is proved that that linear program indeed returns a shortest path.

Even with the newly added constraint $\sum_{e\in E} x_e \le c$ to me it looks like my previous reasoning is still valid.

If that were the case however, we could solve the linear program for $c=1,...,|E|$, and for each solution check whether its weight is negative. If we find any solution for which the weight is negative, we have a path as is requested by the problem.

If all solutions have positive weight, then there is no such path.

As each LP-program runs in polynomial time, and we have to run $|E|$ variations of this program, the whole algorithm should still be run in polynomial time.

This however clashes with the fact that the problem itself is NP-hard.

So, somewhere in my reasoning is a mistake (most likely the result of the linear program doesn't have to be a path anymore or something similar) - however, I simply can't find what exactly is going wrong. Where is it?

Edit:

The reasoning (copied from the previous question) for the correctness of the linear program:

Let $S$ be a solution to above linear program. As the constraints are the same as for network flows (if we see each edge as having infinite capacity), $S$ is a flow on $G$.

Given that every $s-t$-path fulfills the constraints, we can conclude that if $S$  is an  $s-t$-path, then it is an $s-t$-path with minimal costs.

Further, $S$ can't contain any cycle with positive weight, as we could simply remove this cycle from $S$ and end up with a lower-cost solution that fulfills the constraints.

Finally, $S$ has to be an $s-t$-path. Let's assume $S$ wasn't. Given that $S$ is a flow, we know that it has to contain some $s-t$-path. So let $M$ be the set of all $s-t$-paths that $S$ contains.
 Then there is a path with minimal costs in $M$ (as $S$ is cycle-free, and therefore there can only be finitely many elements in $M$). Let this $s-t$-path be $p_{min}$.

If we let $c: M\to \mathbb R $ now be the map that assigns each $s-t$-path in $M$ its cost, we obtian the following inequality:
$$1\cdot p_{min} \le \sum_{p\in M} \lambda_p \cdot p \qquad\text{ given that } \forall p\in M: \lambda_p \ge 0 , \sum_{p\in M} \lambda_p = 1$$

Therefore, if $S$ would contain multiple $s-t$-paths, it wouldn't be minimal.

Thus we can conclude, that $S$ is a minimal $s-t$-path.


texts: What is the advantage of Day-Stout-Warren algorithm for balancing BST?

texts:
While reading about Day–Stout–Warren algorithm for balancing BST which takes any BST and transforms it into a balanced BST in O(n) time.

In my opinion I can achieve absolutely the same with these simple steps:

convert BST into array using inorder traversal. This will give me an array in increasing order and can be completed in O(n)
create a binary search tree by selecting the middle element in array in O(1), put it as a root, and recursively do the same for a right part of an array (putting the value as a root for a right subtree) and the same for the left part. This will also run in O(n)

So in my opinion I can achive absolutely the same in O(n). What is the advantage of DSW algorithm in comparison to this one?


texts: Is it always possible to have one part of the reduction?

texts:
So I have been asked this question during my comprehensive and I have a few answers to it, I just wanted to check with the community whether I'm on track with them.

Is the following statement true?

$\forall A,B \subseteq \Sigma^{*}, \exists\ f : \Sigma^{*} \rightarrow \Sigma^{*}, s.t. \forall x \in A \implies f(x) \in B $

The function  $f$ had to be decidable in polynomial time, as in the notion of reductions. So, the question in english stands as, is it always possible to find a polytime computable function of the like written above, for any two languages, s.t. one direction of the notion of reduction holds.

So, at that moment I couldn't argue for polytime computability, but , the obvious idea of having a map from $\Sigma^{*}$ to an element in B, was all I could come up with. Later, on subsequent thinking I realised that it basically becomes a membership checking question for arbitrary B. Another idea, also struck and that being when B $\ =\ \phi$, then $(A,\phi)$ serve as the counterexample sought, where A is any language.

So, in case we do not allow for B being the empty language, any instance of B which is undecidable or rather, takes more than polynomial time for membership checking [Not sure about the second one as its unknown whether P!=NP] holds, right?

Other questions associated to this, are:

(1) if A=3SAT and B $\in \mathbb{P}$ , then does the existence of such a  $\ f$, prove P=NP or do you need the reverse direction of reduction to hold as well, to conclude that?

(2) What about when $\ f$ is allowed to be decidable, or semidecidable, what changes?

(3)And, what if the reverse direction of reduction was the condition to be satisfied by $\ f$, ie, $\forall x \in \Sigma^{*},\  f(x) \in B \implies x \in A$ then what changes? [ I worked this out, taking the contrapositive , ie, $\forall x \not\in A \implies f(x) \not\in B$ it basically boils down to membership checking for the complement language, ie, $\overline{B}$ ]

EDIT : Sorry (1) was trivial. As pointed out by the answer below, $\mathbb{P} \subseteq \mathbb{NP}\ $ means I can just use the same f trivially for the reverse direction.


texts: Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?

texts:
Karp's 21 NP-complete problems show that 0-1 integer linear programming is NP-hard. That is, an integer linear program with binary variables.

If we set the $c^T$ vector of the objective $\text {maximize } c^Tx$ to all one (unweighted, i.e., $c^T=(1,1,\dots,1)$) is the problem still NP-hard?


texts: How to traverse a graph in reverse dfs order

texts: For kosaraju's algorithm to traverse  the graph in reverse order the naive solution is to reconstruct the original input graph in reverse order and dfs on it. Is there any way I can avoid creating copy of the graph in reverse order? how can I dfs on the same original graph going back across the edges?


texts: Help with question involving k-regular graphs

texts:
In my last test, our teacher gave us this question:

  In an conference with 90 participants, the staff wants to divide all
  participants in 6 groups of 15 participants each. Each participant of
  each group must have at least one article with exactly 7 other
  participants of the same group. Prove using Graph Theory that this
  division is impossible.

I spent a lot of time thinking about, but couldn't find an definitive answer. I think that this involve bipartite matching somehow, but I have no idea on how to proceed with the proof. I thought that maybe creating a k-regular graph would prove that this don't have a matching, but I couldn't come with the graph representing the problem.

Can I get some help with this?


texts:
What is the running time of heapsort when the input array is in increasing order? How about decreasing order?  (I came across these questions in CLRS.)

Here is what I have done so far ...

For the increasing order (i.e. the order opposite to the output order) I am completely stuck and haven't been able to make any progress because as I see it as soon as we build the max heap the structure completely changes and I cant reason about what the final heap will look like.

For the decreasing case I feel like I understand what is going on and will try to describe that below, but its also a long way from a proof.
A decreasing array is already a max heap so the array is unchanged by building the max heap.
WLOG assume a complete binary tree (else just remove some elements until you get one)

Remove the first $n/4$ largest elements. The first element will then be lifted to the top and fall back down a distance of $\log n$ falling to the left each time (the left element is always the largest).

But now the right is larger for each vertex that this last element fell through. So the next vertex will first fall right then fall left the rest of the way. No vertex will fall the same path until this has been rectified. So elements moved to the top of the tree continue to fall the full length of the tree. Rectifying the tree seems like it will take a linear time because it has length logn and it feels like you have to go down a constant fraction of the other routes before it is done. But this is really wordy and sort of garbage.

I apologise if this could be written better but I tried my best to say what I mean.

Note I have read the proof for the general best case but I was looking for something more straightforward due to the extra information.

Thanks


texts: What does a faster algorithm mean in theoretical computer science?

texts:
If there is an algorithm running in time $O(f(n))$ for some problem A, and somebody comes up with an algorithm running in time, $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is it considered an improvement over the previous algorithm?

  Does it make sense, in the context of theoretical computer science, to come up with such an algorithm?


texts: Prove that any PDA/CF language with 1 character is regular

texts: I know there is a post like this already posted, but I didn't quite understand the proof. Can someone explain it to me? Thanks in advance.


texts: Why is it better to do the data flow analysis in the basic blocks

texts:
I have been reading about compilers and it is said that doing the data flow analysis in the basic blocks is more optimal.

Sadly, quoting the exact source, would be slightly hard as it is not in English, but a quote from wikipedia can also be used:

Data-flow analysis is the process of collecting information about the way the variables are used, defined in the program. It attempts to obtain particular information at each point in a procedure. Usually, it is enough to obtain this information at the boundaries of basic blocks, since from that it is easy to compute the information at points in the basic block.

Even though, in Wikipedia it is slightly explained, why the basic blocks are the preferred way, I still do not understand the benefits and if it is not obtained from the basic blocks, then from where?


texts: Can someone please show me examples of what is the difference between OLR (one literal rule) and PLR (pure literal rule) using the DPLL algorithm?


texts: What if P implies Q is false when both P and Q are false?

texts:
This is actually a problem that our professor gave us, and I'm clueless of how to answer this. I browsed through various sources, but none were helpful regarding this question.

The question is,

  In the definition of semantics of logic, P implies Q is defined as
  true under the assignment of both P and Q are false. Although this is
  rather unusual at a glance, explain what would be the issue with
  logic, if the definition is differently.

Any helpful answer is highly appreciated.


texts: How do you convert a regular expression to its disjunctive normal form?

texts:
A regular expression $r$ is said to be in disjunctive normal form if it can be written in the form $r = r_1 +r_2 +\dots+r_n$ for some $n ≥ 1$, where none of the regular expressions $r_1, r_2, \dots, r_n$ contains the symbol $+$ (union).

For example, the regular expression $a^*b^* + (ab)^* + (c(acb)^*)^*$ is in disjunctive normal form.

The task is to prove that every regular language can be specified by a regular expression in disjunctive normal form. Considering that every regular language by default can be represented by a regular expression, the question now seems to simplify to proving that any regular expression can be converted to or expressed in disjunctive normal form. Any idea on how that is possible?


texts: Why isn't the Generalized Super Mario Bros. obviously in NP?

texts:
It is shown in the paper: "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta that the Generalized Super Mario Bros. (SMB, for short) video game is NP-hard.

  Theorem 3.1. It is NP-hard to decide whether the goal is reachable from the start of a stage in generalized Super Mario Bros.

(When generalizing the original Super Mario Bros., we assume that the screen size covers the entire level, because the game forbids Mario from going left of the screen.)

However, it does not claim that SMB is in NP.

My problem: Why isn't SMB obviously in NP?

I came up with two reasons.

First, the solution/certificate to SMB may be not of polynomial size, due to e.g., timing. Is this valid? If so, how to argue this point more formally?
Second, the computer can be treated as a second player. Thus, SMB is a two-player game, which may be reasonably harder. However, are the actions of the computer player determined from the beginning of the game so that we can still regard SMB as a single-player game?

Related posts:

What is the whole picture of the NP-hardness proof of Super Mario Bros?
Why are Chess, Mario, and Go not NP-complete?

Added: A follow-up paper also by Erik Demaine (et al.) which shows that a generalized level of SMB is PSPACE-complete.


texts: Why this set cover greedy-like algorithm is not $\log k$-approximation for bin packing problem?

texts:
Bin packing: Given a set of $k$ items where item $j$ has size $s_j$ and a set of bins of capacity $C$ each. Use the minimum number of bins to pack all items while respecting the capacity of the used bins.

If I select one bin arbitrarily and put in it the maximum possible number of items and repeat this until no item is left. Why I won't get a logarithmic factor approximation algorithm as in set covet problem?


texts: Variant of interval scheduling with varying task durations

texts:
I am probably just missing the correct term for my problem to find the solution but here it goes:

I have a set of tasks with a given duration and an interval for each task in which it has to be completed. I now need to find start times for the tasks, so that

each tasks is completed within its interval
no task overlaps with another task

Sketch:


texts: Are all turing complete languages interchangeable

texts:
Note, while I know how to program, I'm quite a beginner at CS theory.

According to this answer

  Turing completeness is an abstract concept of computability. If a language is Turing complete, then it is capable of doing any computation that any other Turing complete language can do.

And any program written in any Turing complete language can be rewritten in another.

Ok. This makes sense. I can translate (compile) C into Assembly (and I do it everyday!), and can translate Assembly into C (You can write a virtual machine in C). And the same applies to any other language - you can compile any language into Assembly, and then run it in a VM written in another other language.

But can any program written in a Turing complete language be re-written in another?

What if my Assembly has a LIGHTBUTTON opcode? I physically can't emulate that language on a system (language) without a lightbulb.

Ok. So you'll say that since we're dealing with computer theory, we're not discussing physical device limitations.

But what about a device that doesn't have multiplication? division? To the best of my knowledge (though this is more of a question for math.SE), one can't emulate multiplication (and definitely not division) with addition and subtraction [1].

So how would a "turing complete language" (which can add, subtract, and jump) emulate another language which can add, subtract, multiply and jump?

EDIT

[1]. On arbitrary real numbers.


texts: I do not understand what is a ridge for hill climbing. The definition I found is a place where all points appear like a maximum, but how is that different than a plateau?


texts: Non intersecting paths of graphs with obstacle number one

texts: There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but what about non-intersecting Hamiltonian path?


texts:
i am trying to understand the DES cryptosystem and was wondering: what would've happened if all of the sub-keys were equal? does it reduce the security? can we actually find the keys if we know all the sub keys are equal?

can we make this any securer if for instance we run DES twice?

if you can give me a mathematical explanation it would help me a lot in understanding why things are happening so i can better understand this algorithm.

thank you much for assistance!


texts:
Given an array, I need to sort the array (if not already sorted) in either decreasing or increasing order so that number of swaps are minimized.

I was thinking of first determining whether it is increasing type or decreasing type i.e. the type in which least swaps would be required and then sort my array in increasing or decreasing order accordingly. I don't know how to implement in determining the type. Can someone help me in finding heuristic or algorithm to do so ?

Also if the array is 2-Dimensional, would the idea still work or will I use less swaps if I change elements between rows instead of within the row itself. And if it has to be inter-row, how would I go about for that such that all rows are sorted (a row can be either increasing or decreasing) ?


texts: Independent set on cubic triangle-free graphs

texts:
I know that maximum independent set on cubic triangle-free graphs is NP-complete.

Is it still NP-complete in case we require the independent set to be of size exactly $|V|/2$?

Basiclly, YES instance of independent set problem on cubic triangle-free graphs problem must have exactly $|V|/2$ nodes. NO instance has an independent set of size less than $|V|/2$.


texts: Intellij string search and highlight algorithm

texts:
I'm searching for an alogrithm that takes two strings, a query and a string that is to be searched for the query. The algorithm should result in a 'found' when the string contains the characters of the query in the right order but with any amount of other characters inbetween.
Example: query:'abc', string to search: 'xaxbxc' results in 'found', because 'xaxbxc' contains the characters 'a', 'b' and 'c' in that given order.
Furthermore the algorithm should be able to highlight the found query in the searched string.
Intellij IDE such an algorithm for searching files. Given a file 'settings.ts' Intellij File search (Ctrl+Shift+N) gives the following results for the given search input.

A naive solution would be to start with the first character in the query and loop through the string to be searched until the first query character is found. Then go to the next query character and search for it in the searched string starting from where the first query character was found and so on. If all query characters were found yield true.
This results in two problems:

It should be very slow compared to Boyer-Moore-Search, but i can limit the strings to be searched using triplet indexing as Intellij does
the highlighting is "wrong": the stated algorithm would correctly identify 'settings.ts' for the given query 'sets' but would highlight the wrong way (highlighting of the given algorithm: settings.ts), Intellij highlight as seen above: settings.ts

In other scenarios this is much more dramatic: given query: 'hours', search string: 'The sun rises above the mountain in the early morning hours' this would highlight:
The sun rises above the mountain in the early morning hours
 ^              ^         ^               ^               ^

instead of:
The sun rises above the mountain in the early morning hours
                                                      ^^^^^

I suspect some kind of levensthein-esque algorithm to get the highlighting correct by penalizing single characters in highlighting with a higher cost.
Does someone know what algorithm Intellij uses for search highlighting? Thanks in advance!


texts: Algorithm to match timestamped events from two sources

texts:
does a good known algorithm exists for this problem?

On input I have two series of timestamps "when the event was observed". Theoretically the recorded timestamps should be very well aligned.

Visualized ideal situation on two time lines "s" and "r" as recorded from the two devices:

but more likely they will not be so nicely aligned and there might be missing events from timeline s or r:

I am looking for algorithm to match events from "s" and "r" like this:

So that the result will be something like: (s1,r1); (s2,r2); (s3,null); (s4,r3);(null,r4)... Or something similar. Maybe with some "confidence" rating.

It feels like there should be some well known algorithm for this problem, but I am a bit out of my element here.

Thanks.


texts: Understanding the concept of "Viable Prefixes"

texts:
I was going through the text: Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the concept of viable prefix and I faced some difficultly in grasping the concept. So I present my doubts here in a systematic manner, with a hope for clarification.

Viable Prefixes: The set of prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes.

This is the actual definition. No problem with it, since it is a definition after all.

An equivalent definition of a viable prefix is that it is a prefix of a right-sentential form that does not continue past the right end of the rightmost handle of that sentential form.

I do not quite understand why "the rightmost handle"? And why not the leftmost handle?
Is it so because of grammars like:

can have the two possible rightmost derivations for $id_1+id_2*id_3$:
 Derivation (1)
 Derivation (2)
where for the right sentential form $E+E*id_3$ there are two handles:
left: $\require{color}\colorbox{pink}{E+E}*id_3$ and
right: $E+E*\require{color}\colorbox{pink}{$id_3$}$

By this definition, it is always possible to add terminal symbols to the end of a viable prefix to obtain a right-sentential form.

Is it something like this, Suppose
$$(1) S \xrightarrow [\text{rm}]{\text{*}} ABCDE \xrightarrow[\text{rm}]{\text{*}} ABpqr$$
$$(2) S \xrightarrow [\text{rm}]{\text{*}} ABCDE \xrightarrow[\text{rm}]{\text{*}} ABxyz$$
So adding terminals $pqr$ or $xyz$ to the viable prefix $AB$ we can get a right sentential form...

Therefore, there is apparently no error as long as the portion of the input seen to a given point can be reduced to a viable prefix.

This I feel from the actual definition is true, because a viable prefix is a prefix appearing on the stack...

Is my understanding fine? If not please rectify me.


texts: Sorting algorithms which accept a random comparator

texts:
Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the algorithm is a sorted list/array.

I am wondering though which sort algorithms would actually work with a comparator that is not an order relation (in particular one which returns a random result on each comparison). By "work" I mean here that they continue return a permutation of their input and run at their typically quoted time complexity (as opposed to degrading to the worst case scenario always, or going into an infinite loop, or missing elements). The ordering of the results would be undefined however. Even better, the resulting ordering would be a uniform distribution when the comparator is a coin flip.

From my rough mental calculation it appears that a merge sort would be fine with this and maintain the same runtime cost and produce a fair random ordering. I think that something like a quick sort would however degenerate,  possibly not finish, and not be fair.

What other sorting algorithms (other than merge sort) would work as described with a random comparator?

For reference, a comparator is an order relation if it is a proper function (deterministic) and satisfies the axioms of an order relation:

it is deterministic: compare(a,b) for a particular a and b always returns the same result.
it is transitive: compare(a,b) and compare(b,c) implies compare( a,c )
it is antisymmetric compare(a,b) and compare(b,a) implies a == b

(Assume that all input elements are distinct, so reflexivity is not an issue.)

A random comparator violates all of these rules. There are however comparators that are not order relations yet are not random (for example they might violate perhaps only one rule, and only for particular elements in the set).


texts: Can we get a better time hierarchy theorem?

texts:
The time hierarchy theorem states that

$DTIME(f(n)) \neq DTIME(f(n)\log(f(n)))$

(Let me acknowledge that this statement isn't 100 percent accurate because f must be "time constructible" and potentially other things that I'm missing)

If we were to take some function f, we can consider

$DTIME(f(n)) \subset DTIME(f(n)\sqrt{\log(f(n))})\subset DTIME(f(n)\log(f(n)))$

Where we know that at least one of these inclusions is strict. Do we know of examples where one of these inclusions isn't?

In general we might want to prove that
$DTIME(f(n)) \neq DTIME(f(n)g(f(n)))$
for a function $g$ which is as small as possible. Do we have better upper bounds on $g$ (like $g(n) = \log\log n$)? do we have non-trivial lower bounds on $g$ in the form of some (time constructible) $f$ for which $DTIME(f(n) = DTIME(f(n)g(f(n)))$?


texts: How can i design this function using only NAND and XOR gates?

texts:
I have this initial function \begin{split}(\overline{A}+\overline{B})(\overline{D}+\overline{C})+AB\overline{(\overline{C}+\overline{D})}\end{split}
Which i reduced to \begin{split}{\overline{AB}*\overline{CD}}+ABCD \end{split}
The first part is easy to do with NAND but the OR ABCD part i have no ideia how to do...I suspect thats where the XOR comes in and i maybe shouldn't have reduced so much the function.


texts: Validity of Algorithm for Testing Two Floating Point Numbers

texts:
This question is related to the epsilon- (or delta- if you prefer) test for floating point equality. But my question is not how to do it. Instead I have a related algorithm for testing equality, and I would like feedback as to what might be wrong with it.
The idea is to take the quotient of two floating point numbers and compare it to one. This eliminates the difficulty of choosing a value for epsilon. I have tested it extensively and am happy with the results. Here is a sample implementation in Java.
public class DoubleEquals
{
    public static final double  EPSILON = 1e-14;

    public static boolean equals( double param1, double param2 )
    {
        // Accounts for 0, +/-INFINITY;
        // if both values are NaN the result will be false
        boolean result  = param1 == param2;
        if ( !result )
        {
            double quot = param1 / param2;
            result = quot > 0 && (1 - quot) < EPSILON;
        }

        return result;
    }
}
```


texts: Proof regular languages are closed under homeomorphism

texts:
Let $\Sigma_1 , \Sigma_2$ be alphabets. Let $L\subseteq \Sigma_1^*$ be a regular language, and let $ h:\Sigma_1^* \rightarrow \Sigma_2^* $ be a homomorphism.
Proof $h(L)$ is regular.
I have written a proof using induction over the number of operands in the regular expression $r$ such that $L = L(r)$, that there exists a regular expression $r'$ such that $L(r') = h(L)$.
I divided it to three cases:

$r=r_1 \cup r_2$

$ r= r_1r_2$

$ r =r_1^*$

Since functions union might not always be a function (i.e $f(1)=1$, $g(1) =2$ $\rightarrow f\cup g$ not a function)
I would like to get your opinion for the union case, to verify I didn't do anything wrong there - especially in lines $5,6,7$:

$w\in h(L) \Leftrightarrow w = h(\sigma_1 \dots \sigma_n)\in h(L) \wedge \sigma_1 \dots \sigma_n \in L \Leftrightarrow $
$\sigma_1 \dots \sigma_n \in L(r_1 \cup r_2) \Leftrightarrow $
$\sigma_1 \dots \sigma_n \in L(r_1) \cup L(r_2) \Leftrightarrow $
$\sigma_1 \dots \sigma_n \in L(r_1) \vee \sigma_1 \dots \sigma_n\in L(r_2) \Leftrightarrow $
$h(\sigma_1 \dots \sigma_n) \in h(L(r_1)) \vee h(\sigma_1 \dots \sigma_n) \in h(L(r_2)) \Leftrightarrow $
$h(\sigma_1 \dots \sigma_n) \in h(L(r_1)) \cup  h(L(r_2)) \Leftrightarrow $

Now, using the induction hypothesis, since $r_1$ and $r_2$ has less operands,

$h(\sigma_1 \dots \sigma_n) \in L(r_1') \cup  L(r_2') \Leftrightarrow $
$w \in L(r_1' \cup r_2') $

Is this a valid proof for this case?


texts: Is there any general, theoretical limit to time - space tradeoff?

texts:
In many algorithms, one can spot that improvements in time often are occupied by more memory requirements. For example usage of cache allows to speed up calculations by saving results in memory.

Is there any theoretical limit of "time-space tradeoff" similar to Amdahl's law limiting speed-up from the parallelization of calculations?

Example

Assumption: we will neglect the size of the call stack.
To illustrate how time-space tradeoff works let us think about Fibonacci sequence calculations.
One can calculate Nth Fibonacci seq. element using the below equation:

fib(n) = fib(n-1) + fib(n-2)
fib(1) = fib(2) = 1

Notice, that to compute Nth element we need to calculate 2 previous ones. To calculate each of these we need to calculate 2 previous ones for each of them and so on...

Straightforward implementation be:

function fib(n) {
  if (n == 1 || n == 2)
    return 1;
  return fib(n-1) + fib(n-2);
}

Let's visualize this using graph for N=6:

Notice, that some calculations are repeated:

What one can do to speed up algorithm is to remember results of repeated calculations and reuse them. One is trading space for time.

Implementation of such tradeoff:

const resultsCache = [1,1];
function fib(n) {
  if (resultsCache[n])
    return resultsCache[n];
  fibN = fib(n-1) + fib(n-2);
  resultsCache[n] = fibN;
  return fibN;
}

Question

Is there any theoretical limit of "time - space tradeoff" as presented in above example? It is how much we can speed up algorithm by using more space?


texts:
I see a lot of lecture notes where they use the term "congruence" (ex: congruence relation) or deriving usages such as "the expression e is alpha-congruent to e2".
Could someone please explain what congurence means exactly in this context and give some examples to a noob without much knowledge about math/lambda-calculus.
Thanks in advance


texts: Given a DFA A, give a formal construction of a PDA with three states M such that L(A) = L(M)

texts:
given a Deterministic Finite Automata, I am looking for a formal construction of Push Down Automata with 3 states such that the languages of the DFA and the PDA are the same. How we can prove correctness?

Any help appreciated.

Thanks!


texts:
I have seen that in the material made by Andrew Ng about neural networks, he uses the following weights:

so when I replace the final values of h_theta(x) in the formula:

I got values near 0 and 1.

The problem that I have is when I use the values that are in the Tom Mithell book about Machine Learning, he uses the values w0=-0.8, w1=w2=0.5. I have performed the calculations and got the values of h_theta(x) as the following:

0.8,0.3,0.3,-0.2

but when I replace these set of values into the formula of the sigmoid function I got:

0.31,0.42,0.42,0.54

that does not differentiate too much about which values are near 0 and which near 1, something that did not occur with the values that Andrew Ng proposed for the weights. Am I missing something? in this case it would be better to select big values for the weights instead of small ones?

Any help for clarifying this is welcome


texts: Tiling an orthogonal polygon with squares

texts:
Given an orthogonal polygon (a polygon whose sides are parallel to the axes), I want to find the smallest set of interior-disjoint squares, whose union equals the polygon.

I found several references to slightly different problems, such as:

Covering an orthogonal polygon with squares - similar to my problem, but the covering squares are allowed to overlap. This problem has a polynomial solution (Aupperle, Conn, Keil and O'Rourke, 1988;  Bar-Yehuda and Ben-Hanoch, 1996).
Tiling/decomposing/partitioning an orthogonal polygon to rectangles. This problem has a polynomial solution (Keil, 2000; Eppstein, 2009).
Covering an orthogonal polygon with rectangles - this problem is known to be NP-complete (Culberson and Reckhow, 1988).

I am looking for an algorithm for minimal tiling with squares.


texts: Why do register machines outperform stack machines?

texts: Wikipedia says stack machine “designs have though been routinely outperformed by the traditional register machine systems, and have remained a niche player in the market.” Why is this?


texts: Measuring distance in arbitrary scale point cloud

texts: I have one point cloud(point cloud of human feet) of arbitrary scale. If I have another point cloud(of human feet) with dimensions known, can I get the dimensions of a first point cloud? How will scaling work here?. Please feel free to give references as I am new to computer vision.


texts:
A language $L$ is in NP if and only if there exist polynomial $q$, and a deterministic polynomial Turing machine $M$ such that, for all $x\in L$, there is a string $y$ such that $|y|\leq q(|x|)$ and $M(x,y) = 1$.

My question is is it possible to exchange $M$ for a finite automaton?

Thank you


texts:
This question is specifically related to

https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm

The $gcd(x,y)$ is solved in $O(T(n) log n)$, where $n$ is the number of bits of $x,y$, and $T(n)$ is the time to multiply two $n$ bit numbers, as described in

How is the Time Complexity of a Function Problem different than its corresponding Decision Problem?

so when it reads "if you're dealing with big integers, you must account for the fact that the modulus operations within each iteration don't have a constant cost. Roughly speaking, the total asymptotic runtime is going to be $n^2$ times a polylogarithmic factor. Something like n^2 lg(n) 2^O(log*n). "

Isn't this the same thing as stating "the fastest $gcd(x,y)$ is solved in n^2 lg(n) 2^O(log* n)"?  If so, then

How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?

If the $gcd(x,y)$ is solved in $O(T(n) log n)$, shouldn't this be true no matter how large $n$ is?


texts: Calculate the number of distinct permutations of length n in the closure of a language

texts:
I am studying a distance CS course, but there is no tutor available, so I would appreciate your help...

Consider the language $S = \{a, aa, ab\}$
How many distinct words of length $n$ will appear in $S^*$?

Is there a way to do this without having to "enumerate" $S^*$ until the answer is found?


texts:
I am reading Exploring Robotic Minds by Prof. Jun Tani, and came across the term subrecursive. Original context:

  Another possibility might be to assume subrecursive functions embedded in analogical processes rather than logical operations in FLB that can mimic recurssive operations for finite levels.

FLB is Noam Chomsky's faculty of language in a broad sense

I am have found the following definition from Campagnolo et al., but am having a hard time understanding it. Any help unpacking the following or an example would be greatly appreciated :)

  All functions in the Grzegorczyk hierarchy are subrecursive, meaning that they are computable in a number of steps which is a less computationally complex function of the input than the function itself

Bonus question

Are subrecursive algorithms the opposite of superrecursive algorithms? In either case can you help me understand the relationship between them?


texts: What Measure of Disorder to use when Analysing Quicksort

texts:
I'm trying to understand why quicksort using Lomuto partition and a fixed pivot is performing erratically, but overall poorly, on randomly generated inputs.  I'm thinking that even though the inputs are randomly generated, there may be a lot of order to the sequences, but I'm not sure how to measure the level of disorder in the sequences.  I thought about using the number of inversions, but I saw from this other question I asked that that's not really a good measure in this case.

The reason I suspect that my random sequences have a lot of "order" to them is that randomizing the pivot fixes the performance problem.  But theoretically there shouldn't be any performance problem on these supposedly "random" input sequences.


texts: Time complexity of a vertical sweep algorithm with histogram computations

texts:
In the paper

Quick Detection of Brain Tumors and Edemas: A Bounding Box Method
Using Symmetry, Saha et al

the authors claim that the running time of the algorithm (Matlab implementation) is $O(h)$. I don't understand how they arrive at this.

The algorithm works as follows:
The algorithm does a vertical sweep of a whole image of size $h\times w$.
For every $l$ between $0$ and $h$, a score function $s$ is computed.
To compute $s$ we we calculate histogram computation of the four parts of the whole image : $[0:l,1:w/2]$, $[l:h,1:w/2]$, $[0:l,w/2:end]$ and $[l:end,w/2:end]$.

How do they arrive at $O(h)$ time complexity for the algorithm? Do they consider histogram computation to be $O(1)$?

PS: This question is related to What is the time-complexity of histogram computation? but I hope to get the exact answer in concrete case this time ...


texts: Recurrence relation of the coin change problem

texts:
I'm trying to wrap my head around the coin change problem, where you try to find the total number of ways $N$ cents can be exchanged using $M$ coins $\{C_1, C_2, ..., C_m\}$.

The recurrence relation is this:

I'm having difficulty understanding the 3rd line where it says solution[i][j-v[i-1]]. What exactly is this v they are talking about? I understand it's just the array index above the current one being worked on, but I still don't get what this v is. Can anybody explain please?


texts:
Given that any implementable algorithm has a finite number of internal states, and given that any state is determined by the previous one, does that implies that any algorithm loops at some point?
If I run the algorithm until the number of state transitions is greater than the number of internal states, by the pigeonhole principle, I should eventually get into a loop. Is that correct?


texts: Find equivalent LTL formula, without Y (Yesterday) operator. How can I handle first state?

texts:
The task is to find an equivalent LTL formula for $G(a \Rightarrow Yb)$, which doesn't contain the Y operator. My idea is to search for invalid path patterns with 2 $a$'s in a row, e.g. bbbbaab.

Therefore I'm thinking of $G(Xa \Rightarrow b)$, so whenever an $a$ occurs in the next state the the current state must be true for $b$. But I have a problem with the starting states. Consider a path starting with $a$, e.g. s3->s4->... this path would be false for the original formula (iv), since Yb is always false for the first state. But this exact state would be true for the formula $G(Xa \Rightarrow b)$.

How do I have to modify my formula to also cover the starting states correctly?


texts: Finding a '1' cell with a '0' to its right in a binary array

texts:
Given an array of size n that holds ones and zeros I need to find an index of a  1 cell that has 0 to his right (in then next cell) there could be more than one pair in a given array, any one of them is fine. The array is not sorted, but we do know that the first element is 1 and the last element is 0.

The search should be in $O(\log n)$ time. I'm thinking that a binary search variation is the answer but I'm not sure how.


texts: What is the natural language of computers mathematics or logic?

texts:
I was reading about the history of computers where i came by machine code

  A Machine code or machine language is a set of instructions executed directly by a computer's central processing unit (CPU). Each instruction performs a very specific task, such as a load, a jump, or an ALU operation on a unit of data in a CPU register or memory.

The computer here does logical operations like load or jump steps using the machine code.

From the Wikipedia page a computer is

  A general-purpose device that can be programmed to carry out a set of arithmetic or logical operations automatically.

This means from the machine code the computer can perform logical or arithmetic operations, but which principle computers are based on  the logical principle or the mathematical principle ?

What can be said also as the natural language of a computer ?

====

[Edit] both answers solved my problem.

====


texts: Intersection/Union of Language of PDA, CFG and NFA

texts:
I stumbled across the following question.

Say I have given an arbitrary PDA $P$, NFA $N$, and CFG $G$. My question is then if the following language ($L(P) \cap L(N)) \cup L(G)$ is context-free.

How can this be determined?


texts: Number of strings accepted by this regular expression

texts:
This was a question that I got while taking a test at our university. The question paper was taken away after the exams. I remember the question only, not the multiple choices.

If a regular expression is of the form (x+y)*y(a+ab)* , then what is the maximum number of strings with length 4 will bee accepted by its language?

I've tried simplifying the expression, or drawing FSM diagrams but can't figure it out. A little help would be appreciated.

Thank you!


texts:
Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online.

$x\; \mathrm{XOR} \;y\; \mathrm{XOR} \;z = ((x|y)(\neg x|y)|z) (\neg ((x|y)(\neg x|y))|z)$. This is way too complicated and time consuming to draw. Isn't there another way?

Thank you for taking the time!


texts: Find all sets of n unique rows in matrix


texts: Finding maximum clique in a distance matrix created by certain pattern

texts:
I have a distance matrix which is created through a predefined pattern (or formula) and I want to find elements with minimum distance "d" from each other, in order to do that I search for the maximum clique in the graph which is created with distance matrix.

Knowing that there exists a pattern in the distance matrix can I find the maximum clique more efficiently?


texts: Union of finite and non-regular language

texts:
Question: ($B$ and $C$ are languages)
$B$ is finite,$C$ isn't regular:

Prove/Disprove: $C\cup B$ isn't regular.

Thoughts:
My intuition says this is true, but I need an idea to prove it. Since I don't know if $C$ as a CFG or RE language I don't know what kind of machine I can build for it.


texts:
I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks?

More formally, given two points $a$ and $b$, and energy functional $E(C)$, where $C$ is a curve such that $C(0)=a$ and $C(T)=b$, I want:
$$ C^*=\arg\min_C E[C]=\arg\min_C \int_0^T E_p(C(t))\,dt $$

Essentially, I'd like a solution to a variational curve problem.

I have looked at path-planning, but these tend to be looking at graphs or other paths in discrete spaces.

Another idea is to place points, construct a spline between them, and integrate the energy measure over the spline.
But how can I do gradient descent on the points' positions to iteratively improve them?

Edit (081517): just to clarify some things, thanks to the comments. I am looking for techniques for curve construction, where I am given an energy functional $E$ (computed by integrating a point-wise energy $E_p$ over the curve) and two endpoints $a,b$ in a space $M$. It could be a Riemannian manifold, but for now $\mathbb{R}^n$ is sufficient. $E_p$ may depend on derivatives of $C$, as in standard calculus of variations.

In other words, I want an algorithm that does the following:

$$\text{Input: } a,b,E \;\rightarrow\; \text{Output: a curve } C \text{ that minimizes } E(C)$$

For example, let $M=\mathbb{R}^{n}$, $n=10$, $v:\mathbb{R}^{n} \rightarrow\mathbb{R}^{n} $ be a vector field, $f_i:\mathbb{R}\rightarrow\mathbb{R}$ be a function, $C(t)\in\mathbb{R}^n$, and $\gamma_i,\eta_i,\alpha\in\mathbb{R}$, with point-wise energy:
$$ E_p[C(t)]=\alpha\,\text{div}(v(C(t))) + \sum_i\gamma_i[ C'(t)_i - \eta_if_i(C(t)) ]^2  $$
where $C'(t)_i = \partial_t C_i(t)$ is the derivative of the $i$th component.

My guess is that $C$ should be given in some kind of spline form, i.e. a set of points $P$ with some associated spline parameters $S$. Then we can optimize over $P$ and $S$ to optimize $E$.

Edit (081517)$^2$: based on the comments below, I'm going to look at the ODE defined by the Euler-Lagrange equations of my example function. I get:
\begin{align}
\frac{\partial E_p}{\partial C_k}
&= \alpha\sum_j \frac{\partial^2 v_j}{\partial C_j^2} - 2\sum_i \gamma_i\eta_i\frac{\partial f_i}{\partial C_k}[\dot{C}(t)_i - \eta_if_i(C(t))]\\
\frac{d}{dt}\frac{\partial E_p}{\partial \dot{C}_k}
&= 2\gamma_k[\ddot{C}(t)_k - \eta_k\sum_j \frac{\partial f_k}{\partial C_j}\dot{C}(t)_j
\end{align}
So I get a system of $n$ second-order (coupled implicit) ODEs:
$$ \frac{\partial E_p}{\partial C_k} - \frac{d}{dt}\frac{\partial E_p}{\partial \dot{C}_k} =0 $$

Questions:

How do I solve this for $C$?
Is there no other standard approach for doing this? (E.g. via optimization)


texts: What is the Memory Bandwidth Usage in a Program Related to?

texts: We can use performance counter tools to check the memory bandwidth usage while a program is running. I want to ask what is this memory bandwidth related to? What parameters are involved in memory bandwidth usage difference between programs with the same functionality but different programming designs?


texts: Production is said to be of the form $u \to v$. I want to know if you distinguish $u$ from $v$ giving them some distinguishing names, like LHS/RHS or something alike.


texts:
What's the class of problems solvable in polynomial time with an exponential number of processors?
I am asking this because I'm curious about the class of problems that could feasable be solved on a hyperbolic plane.
On a hyperbolic plane it is possible to construct an exponential number of processors in polynomial time.


texts: Pumping Lemma for $L=\{a^{2k} b^n b^k \mid k\ge0, n\ge0\}$

texts:
$L=\{a^{2k}b^nb^k\mid k\geq0, n\geq0\}$ over alphabet $\{a,b\}$

How do I prove that $L$ is not regular using Pumping Lemma? All the examples I've come across had same exponents all around, and I'm a bit confused how should I write this down.

Should I start with $w=\{a^pb^pb^p\mid p\leq k, p\leq n\}$ where $w$ is a subset of $L$, or how should this be tackled?


texts:
I'm reading about the algorithm of finding the ranks of all points in a 2D plane, I don't understand the time complexity formula for it. It has four steps:

Compute the median of x-coordinates of all point, and divide the plane into two half Left, and Right.
Recursively do 1. then when there is only 1 point, rank(that point)=0.
Sort points by y-coordinate in Left, and Right separately.
Update Right.

I understand the idea of these steps, and 3. has complexity $O(n\log n)$, but the time complexity formula in my book is

$$T(n)=2T(n/2)+\Theta(n),$$

why the last term is not $\Theta(n\lg n)$? That is my current idea is that the $T(n)=\Theta(n\lg^2n)$, by applying master's theorem.