Are there any problems in $P$ which we do not know any $P$ algorithms?

Nice question!  I think the answer is "yes", but I can't prove it.

The answer is not obvious.  You might imagine that if we had a problem with a non-constructive proof that it is in $P$, we might know it is in $P$ without knowing of an algorithm for it.  For instance, here is a reasonable candidate for such a problem:

$$f(n) = \begin{cases} 1 & \text{if $0^n$ occurs in the decimal representation of } \pi \\ 0 & \text{otherwise.}\end{cases}$$

The problem is to compute $f$.

We can prove that $f$ is in $P$, but as far as I know, we don't know of any specific polynomial-time algorithm that we can prove correctly computes $f$.  In other words, we're certain that such an algorithm exists, but we can't write one down that we're sure works.  In particular, we know of an infinite family of algorithms, such that all of them run in polynomial time and one of them is correct; but as far as I know, we don't know which one is correct.  See How can it be decidable whether $\pi$ has some sequence of digits? for details.

So, I suspect that the answer to your question is "yes" and that $f$ is such an example.

You can find more examples at https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs. That page shows examples of problems where we can prove that a polynomial-time algorithm exists, but that proof is non-constructive, in the sense that it does not tell us what the algorithm is.  Now that said, it's possible that this just reflects our lack of current knowledge.  Maybe tomorrow someone will come up with a constructive proof that those problems are in P, i.e., maybe they will come up with a specific algorithm that they can prove is correct and runs in polynomial-time.  But as it stands today, we don't know of any such algorithm.

See also https://cstheory.stackexchange.com/q/4777/5038, https://cstheory.stackexchange.com/q/12162/5038, and Is there an algorithm that provably exists although we don't know what it is?.

At the same time, there is a limited more limited version of the question for which the answer is "no".

If you limit yourself to problems in NP that have a known nondeterministic polynomial-time algorithm, then we can say that the answer is "no" for those problems: for every problem that is known to be in P and is known to have a nondeterministic polynomial time algorithm, we know of a polytime (deterministic) algorithm for it.

It might sound crazy, but it's true.  In particular, one can use Levin universal search to write down an algorithm for such a problem.  The resulting algorithm will have constant factors that make it totally impractical, but we can prove it runs in polynomial time and that it is correct.  See What is a lay explanation for universal search?, Polytime algorithm for SUBSET-SUM assuming P=NP, and Is there a concept for an algorithm computing a function by first finding another algorithm?.


Why not just use FSTs for combining syntactic and semantic analysis?

How useful this would be depends on the level of the Chomsky hierarchy at which the transducer operates:

Regular languages:

A Finite State Automaton (FSA) is represented by its transitions (e.g. via a diagram or a list of triples) and the corresponding transducer can be seen as adding an output to each of the transitions.

Hence, the output is at the same 'granularity' as the input alphabet, which may not always be what's desired for associating semantics with syntax.

The issue is not so much with the `redundant (epsilon) outputs' as the possible need to make semantic decisions at the level of sequences of syntactic elements, modeled in regular languages by a (necessarily fairly messy) nested transducer scheme.

Context-free grammars

More usefully than for regular languages, it is possible to use syntax-directed translation which can be seen as a `transducing' scheme associating a semantic output with a grammatical production.


Given a computable function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$?

Yes it clearly exists; informally you can build such $M$ in this way:

$M$ makes a copy of its input $x$
then without touching such a copy, $M$ decides if $x$ is in $L$ (possibly "destroying" the working copy of $x$),
if $x \in L$ it enters a "subprogram" (set of states) in which all states are accepting and such subprogram uses the copy of $x$ to compute $f(x)$ (leaving the result in the output tape and ending in an accepting state)
if $x \notin L$ it enters a "subprogram" (set of states) in which all states are NON accepting and such subprogram uses the copy of $x$ to compute $f(x)$ (leaving the result in the output tape and ending in a NON accepting state)


What are different ways to provide a semantics to a language?

There are many possible approaches. Here's a few "classic" styles.

Operational semantics (e.g. small step / reduction, or big step)
Denotational semantics (e.g. domain-theoretic, or category-theoretic)
Axiomatic semantics (e.g. hoare logic)

You can also define the semantics of a language through a translation to another language (already having its semantics). CPS transforms could also be mentioned here.

Also note that many languages admit several distinct semantics. Lazy & eager semantics of functional programs are possible, for instance. Prolog also has many different semantics (I recall someone stating "there's no such a thing as THE semantics of Prolog").

Further, concurrent languages like CCS or $\pi$-calculus have a LTS semantics. Game semantics is also used sometimes (but I don't know much about it).

I'm pretty sure there are many other kinds of semantics. I'd be surprised if in the future someone does not invent a new kind of semantics.


Turing machine: errata in computable numbers paper?

The final m-config for the second configuration is an "e".


How to find the best exploration parameter in a Monte Carlo tree search?

The  value  of $C = \sqrt 2$  was  shown to ensure the asymptotic optimality when rewards are in the $[0,1]$ range (Kocsis, Szepesvári, 2006).

In many games, that reward range is straightforward: maximum and minimum possible scores can be translated to 0 and 1 (0 could mean a loss and 1 a win).

The accuracy of this squashing seems to have a minimal impact (e.g. Using Domain Knowledge to Improve Monte-Carlo Tree Search Performance in Parameterized Poker Squares - Robert Arrington, Clay Langley, and Steven Bogaerts - 2016).

Unfortunately squashing isn't always possible.

With rewards outside the $[0, 1]$ range and/or for fine-tuning the Cross Entropy Method works quite well.


UCT1 Algorithm: What does "total number of simulations" mean?

The UCT1 algorithm is actually an algorithm for a multi-armed bandit. There is a machine with several arms. At each round you pull one of the arms and get some reward. Your goal is to maximize your total reward. In this algorithm, $t$ is the round number: $t = 1$ in the first round, $t = 2$ in the second round, and so on.

When using UCT1 to perform Monte Carlo tree search, you treat each explored node as a multi-armed bandit. Monte Carlo tree search consists of several rounds of simulations: in each round a complete game is played out. The value of $t$ for a particular node is the number of rounds at which you passed through the node.

$n_i$ is the number of simulations through the $i$th child, i.e. how many simulations encountered that state in their simulations. A simulation consists of an entire game played out. Once it exits the node it invariably goes through one of its children. So $t$ is the sum of the $n_i$.

You ask:

  I made some images. Is it like this or like this?

It's more like the latter.


Reduce ATM to the language of TM encodings concatenated by a string where the TM accepts both the string and its reverse

Hint
Forget the similarity between $LM$ and $A_{\mathrm{TM}}$, and for an input $\langle M,x\rangle$ of the reduction, try to build a new TM $N$ such that $M$ accepts $x$ if and only if $N$ accepts $0$, i.e. $\langle N,0\rangle\in LM$.
Complete answer

 Given $\langle M,x\rangle$, build a TM $N_{M,x}$ that on any input always simulates $M$ on $x$. Therefore if $M$ accepts $x$, $N_{M,x}$ accepts everything, otherwise $N_{M,x}$ rejects anything. Now we can see $M$ accepts $x$ if and only if $N_{M,x}$ accepts $0$, i.e. $\langle N_{M,x},0\rangle\in LM$. All above completes the reduction.


In fact, NP is not the set of problems that are easy to verify but hard to solve. It is just the set of problems that are easy to verify. NPC, the set of NP-complete problems, is the set of problems that are easy to verify but seem hard to solve.

Your problem is in NP but it isn't NP-complete (unless P=NP), since it's also in P. That is, it can be solved in polynomial time. To prove this, you need to give a polynomial time algorithm that, given a graph $G=(V,E)$, determines whether it contains a clique of size 3. I trust that you are able to do it yourself.


Is Euler's totient function a primitive recursive function?

A computable function is primitive recursive if and only if it can be computed by a program whose running time is upper-bounded by some primitive recursive function. Your function (usually known as Euler's totient function $\varphi$) can be computed in exponential time, and so is primitive recursive.


Proof or refute $n^n = \Omega(n!)$ with the help of Stirling's approximation

Stirling's approximation states that
$$ n! \sim \sqrt{2\pi n} (n/e)^n. $$
This notation means that the ratio between the two sides tends to 1 as $n$ tends to infinity. For your purposes, we can simply write
$$ n! = \Theta(\sqrt{n} (n/e)^n). $$
Since $\sqrt{n} = o(e^n)$,
$$ n! = o(n^n). $$

If all you want to show $n! = O(n^n)$, then as Jukka mentions you can use the simple bound $n! \leq n^n$.


Your problem has been solved by Brouwer in 1979 in his paper Optimal Packings of $K_4$'s into a $K_n$. Quoting from his paper, let
$$
J(2,4,v) = \begin{cases} \lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor - 1 & \text{if } v \equiv 7 \text{ or } 10 \pmod{12}, \\
\lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor & \text{otherwise}. \end{cases}
$$
The maximal number of groups when there are $v$ players, denoted $D(2,4,v)$, is equal to $J(2,4,v)$ unless $v \in \{9,10,17\}$, in which case $D(2,4,v) = J(2,4,v)-1$, and unless $v \in \{8,11,19\}$, in which case $D(2,4,v) = J(2,4,v)-2$.

The more general case in which every pair can appear at most $\lambda$ times has been solved by Assaf in his paper The packing of pairs by quadruples.


The problem falls into one of the following cases:

case (a): There is a unique path from the root to all other nodes (it means that there is only one single path from root to others; this implies that there is only one single path between any other pair of nodes too). If there is only a unique path from source to each node, then there is $O(n^2)$ number of different paths in the graph, you can just find them pick the longest one as the optimal solution using a polynomial time algorithm. You just need a DFS traversal from root and find the length of path to each leaf and choose the longest one.

case (b): But if it's a general rooted graph, i.e. there can be multiple paths from root to other nodes but there is no path from them to the root, then the following theorem holds.
This problem is NP-complete as the actual longest path problem reduces to it. The reduction is as follows. Given an instance of longest path problem $I=(G(V,E), k)$, we build an instance of your problem $I'=(G'(V \cup \{s\},E \cup \{(s,v_1),(s,v_2),...(s,v_n)\}),k+1)$ (The reduction is very strightforward, I keep it short).

In the later case, if you are just looking for a feasible solution. I suggest removing the source node from your directed graph and using the available heuristics for the longest path problem in the resulting graph. Then adding the source to that path.


Constructing a crown graph given an independent set

In the book Kernelization by Fomin, Lokshtanov, Saurabh, Zehavi (which is downloadable as a PDF on the first author's homepage) you find Chapter 4. Crown decomposition.  This should point you to the answer.


Does the naive conversion of a Boolean Formula to CNF have a polynomial or exponential complexity?

Any algorithm necessarily has exponential complexity, since the CNF of a formula can be exponentially longer than the DNF, and the input might be in DNF.


In mathematical logic - the discipline of logic that has interested computer scientists the most - there is a difference between proof-theoretic truth and model-theoretic truth.

Beyond metaphor (of which we are by no means innocent), neither has anything to do with reality, experienced or imagined, and with the idea of truth that is dealt with by empirical scientists, natural philosophers and historians, to which you allude in your question.

Contingent is, to us, another name for a sentence that is satisfiable, but not a tautology. This has to do with its truth equivalence being dependent on the axioms and rules of inference available (proof-theoretic aspect), or on the valuation of its symbols (model-theoretic aspect).

Gödel showed us that these two aspects do not necessarily go together very well, though. Caution is advised.


Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

Let's denote by $u_1,\ldots,u_{2n}$ and $v_1,\ldots,v_{2n}$ the nodes in the two sides of $K_{2n,2n}$ respectively. We remove the $2n$ edges $(u_1,v_1),(u_2,v_2),\ldots,(u_{2n},v_{2n})$ from $K_{2n,2n}$. You can verify the resulting graph is an example showing the approximation ratio of your algorithm is at least $2-1/n$, when the initial cut is $\left(\{u_1,\ldots,u_n,v_1,\ldots,v_n\},\{u_{n+1},\ldots,u_{2n},v_{n+1},\ldots,v_{2n}\}\right)$.


Terminology for worst-case N-complexity on $O(1)$ insert after amortisation

The case, when the operation performs the worst, is commonly called the worst case.

The common name for the optimization you mentioned is de-amortization.

To denote the fact that operations take $O(1)$ on average, you may say that the time complexity of a single operation is amortized $O(1)$.

As far as I know, amortized complexity analysis was first introduced by Robert Tarjan in his “Amortized Computational Complexity”, where you can look up more usages of the term.


No, they're not Turing complete.  The handle inputs of a fixed size.  Also, they can't loop, so will always halt -- it follows that they don't have the ability to perform Turing-complete computation.


Can a programming language be designed to use a fixed amount of memory?

Yes. At least one variant of C supports this. Its call stacks are bounded in size: you can't call functions within functions indefinitely. It is used for embedded devices.


Bin packing first-fit problem in $O(n \log n)$ time

Your solution has $O(n)$ computational complexity but it doesn't implement the first fit algorithm. The thought behind your solution is to insert the items one by one in the given order (that's correct) and to insert the current item in the last bin if it fits in it or to create a new bin if the current item doesn't fit in the current bin (that's wrong).

First of all, this is not what first fit algorithm asks for. You have to insert the current item in the first used bin that it fits in and if it doesn't fit in any already used bin then you will have to use a new one. You shouldn't consider only the last used bin for the insertion, but all the existing bins, that's my point. Additionally as Discrete lizard mentions in his comment, your implementation is wrong even under the wrong perspective.

I will present the correct first fit method using two different algorithms. The first one is sub-optimal, a brute force with $O(n^2)$ computational complexity, because such an algorithm will illustrate better the first fit logic. The second algorithm is the optimal one with $O(nlogn)$ computational complexity.

Now let's consider the first algorithm. We will initially use no bin. As we read the size of each item we will just iterate from left to right over all the already used bins. If we meet a bin where the current item fits (its empty size is at least equal to the size of the current item) then we use this bin, otherwise we have to use a new bin. Note that it will be very helpfull to save the remaining size of each bin and make an update every time a new item is inserted. Bellow I implement this simple solution using C++.

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int n = 0;  // Current number of items

int b = 0;  // Current number of bins

vector<int> IBM;  // Item->bin matching: IBM[i] = bin of i-th item
vector<list<int>> BIM;  // Bin->item matching: BIM[i] = list of items in i-th bin

vector<double> RBS;  // Remaining bin space: RBS[i] = remaining space of i-th bin

int main()
{
    double item_size;  // Current item size
    while (cin >> item_size)  // While there are still items put them in bins
    {
        bool used_bin_used = false;  // Was the current item put in an already used bin?
        for (int i = 0; i < b; i++)  // Iterate over already used bins from left to right
        {
            if (RBS[i] >= item_size)  // If i-th bin has enough space for the current item...
            {
                IBM.push_back(i);  // Current item was put in i-th bin
                BIM[i].push_back(n);  // i-th bin contains the current item
                RBS[i] -= item_size;  // Decrease the available space of the i-th bin
                used_bin_used = true;  // The current item put in an already used bin
                break;  // No more search for current item
            }
        }
        if (!used_bin_used)  // If true, not new bin for current item
        {
            IBM.push_back(b);  // Current item was put in new bin
            list<int> tmp;  // Helping temporary list
            tmp.push_back(n);
            BIM.push_back(tmp);  // The new bin contains the current item
            RBS.push_back(1 - item_size);  // Save the remaining space of the current bin
            b++;  // Increased number of used bins
        }
        // Output current result using numbering starting from 1
        cout << "Item with id = #" << n + 1 << " was put in bin with id = #" << IBM[n] + 1 << ".\n" << flush;
        n++;  // Increased number of items
    }
    // Output bin containing info
    cout << n << " items were inserted in " << b << " bins.\n";
    for (int i = 0; i < b; i++)
    {
        cout << "Bin #" << i + 1 << " contains items: ";
        for (list<int>::iterator it = BIM[i].begin(); it != BIM[i].end(); it++)
        {
            cout << *it + 1 << ' ';
        }
        cout << '\n';
    }
    return(0);
}

Notice that the solution above follows the online fashion. For each of the $n$ items we search linerly $O(n)$ bins in the worst case, so the computational complexity of the above algorithm is $O(n^2)$.

Now let's construct a second, better algorithm. We want to improve the computational complexity of the above algorithm. We would like to reduce the time needed to find the first (leftmost) bin where the current item can fit, which required $O(n)$ time per item. To achieve this goal we can use a segment tree for maximum range queries on the remaining bin spaces. This way every time time a new item is given we can go down the segment tree and find the bin that we should use in $O(logn)$ time for each item. So the computatonal complexity of the algorithm drops down to $O(nlogn)$. We can even follow the online fashion and not require any knowledge about the value $n$, as we did in the previous implementation by doubling the size of the segment tree used every time we have an overflow. The computational complexity will remain $O(nlogn)$ which can be proved using amortized analysis. The C++ implementation of this algorithm is given bellow.

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int n = 0;  // Current number of items

int b = 0;  // Current number of bins

vector<int> IBM;  // Item->bin matching: IBM[i] = bin of i-th item
vector<list<int>> BIM;  // Bin->item matching: BIM[i] = list of items in i-th bin

vector<double> RBS;  // Remaining bin space: RBS[i] = remaining space of i-th bin

vector<double> A;  // Vector with bin remaning sizes used by segment tree

vector<double> tree;  // Vector with segment tree's values

void make_base(int L)
{
    for (int i = A.size(); i < L; i++)
    {
        A.push_back(1);  // New bins will be empty
    }
    for (int i = tree.size(); i < 4 * L + 5; i++)
    {
        tree.push_back(1);  // These values will be overwritten by build
    }
}

void build(int node, int start, int end)
{
    if (start == end)
    {
        tree[node] = A[start];
    }
    else
    {
        int mid = (start + end) / 2;
        build(2 * node + 1, start, mid);
        build(2 * node + 2, mid + 1, end);
        tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
    }
}

void update(int node, int start, int end, int idx, double val)
{
    if(start == end)
    {
        A[idx] = tree[node] = val;
    }
    else
    {
        int mid = (start + end) / 2;
        if(start <= idx && idx <= mid)
        {
            update(2 * node + 1, start, mid, idx, val);
        }
        else
        {
            update(2 * node + 2, mid + 1, end, idx, val);
        }
        tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
    }
}

int query(int node, int start, int end, double val)
{
    if (start == end)
    {
        return(start);
    }
    int mid = (start + end) / 2;
    if (tree[2 * node + 1] >= val)
    {
        return(query(2 * node + 1, start, mid, val));
    }
    return(query(2 * node + 2, mid + 1, end, val));
}

int main()
{
    double item_size;  // Current item size
    while (cin >> item_size)  // While there are still items put them in bins
    {
        if (tree.empty() || tree[0] < item_size)
        {
            int L;
            if (A.empty()) L = 1;
            else L = 2 * A.size();
            make_base(L);
            build(0, 0, A.size() - 1);
        }
        int idx = query(0, 0, A.size() - 1, item_size);
        if (idx < b)
        {
            IBM.push_back(idx);  // Current item was put in idx-th bin
            BIM[idx].push_back(n);  // idx-th bin contains the current item
            RBS[idx] -= item_size;  // Decrease the free space of idx-th bin
            update(0, 0, A.size() - 1, idx, RBS[idx]);  // Update segment tree
        }
        else
        {
            IBM.push_back(b);  // Current item was put in new bin
            list<int> tmp;  // Helping temporary list
            tmp.push_back(n);
            BIM.push_back(tmp);  // The new bin contains the current item
            RBS.push_back(1 - item_size);  // Save the remaining space of the current bin
            update(0, 0, A.size() - 1, idx, RBS[idx]);  // Update segment tree
            b++;  // Increased number of used bins
        }
        // Output current result using numbering starting from 1
        cout << "Item with id = #" << n + 1 << " was put in bin with id = #" << IBM[n] + 1 << ".\n" << flush;
        n++;  // Increased number of items
    }
    // Output bin containing info
    cout << n << " items were inserted in " << b << " bins.\n";
    for (int i = 0; i < b; i++)
    {
        cout << "Bin #" << i + 1 << " contains items: ";
        for (list<int>::iterator it = BIM[i].begin(); it != BIM[i].end(); it++)
        {
            cout << *it + 1 << ' ';
        }
        cout << '\n';
    }
    return(0);
}

Finally I would like to mention that first fit is a method that doesn't minimize the number of bins used. Solving this problem optimally is NP-hard. First fit algorithm is just a method that usually provides an acceptable solution in a fast manner. It is often used in practice when speed is preffered over optimallity.


Suppose $L \in \mathsf{coRP}$, so that $\overline{L} \in \mathsf{RP}$. Using an oracle to $\mathsf{RP}$ we can determine whether a given string $x$ is in $\overline{L}$, and so whether $x \in L$. This gives a $\mathsf{P}^{\mathsf{RP}}$ algorithm for $L$.


Dynamic Shortest Path with Linear Programming

Our matrix is modelled as a graph $G = (V,E)$ with directed edges $E$ between cells $V$. We denote $V_{kl}$ as the set of nodes $j$ that respect $d_{jl} \leq k$. The edges $E$ exist between all nodes $j \in V_{kl}$ and node $l$, for any $l \in V$. Activated edges represent movements (such as players moving with the ball to an adjacent cell or passing the ball to a faraway agent). All player actions (moving, kicking or passing) take exactly $1$ action, therefore the weight of all edges in our graph is always $1$. Throughout this paper, unless specified otherwise, we use $i \in [1, p]$ to identify an agent, $t \in [0, T]$ to identify different timesteps and $l,j \in V$ to identify nodes. We must define the position and movements of each agent $i$, as well as the position and movements of the ball, all across $t$. Assuming $l_1 \in V_{1l}$ and $l_k \in V_{kl}$, then

\begin{equation}
  \begin{split}
    A_{ijt} = &
    \begin{cases}
      1     ,& \textrm{if Agent $i$ is on cell $j$ at timestep $t$}    \\
      0     ,& \textrm{otherwise}
    \end{cases} \\
    Y_{ill_1t} = &
    \begin{cases}
      1     ,& \textrm{if Agent $i$ moved from cell $l$ at timestep $t$ to cell $l_1$ at timestep $t+1$}    \\
      0     ,& \textrm{otherwise}
    \end{cases} \\
    B_{jt} = &
    \begin{cases}
      1     ,& \textrm{if Ball is on cell $j$ at timestep $t$}    \\
      0     ,& \textrm{otherwise}
    \end{cases} \\
    X_{ll_kt} = &
    \begin{cases}
      1     ,& \textrm{if Ball moved from cell $l$ at timestep $t$ to cell $l_k$ at timestep $t+1$}    \\
      0     ,& \textrm{otherwise}
    \end{cases}
  \end{split}
\end{equation}

These definitions inherently model the behaviour of our agents and ball, by limiting agents to only move $1$ unit of distance at most, and the ball to move $k$ units of distance at most. Both $B_{j0}$ and $A_{ij0}$ are defined for all $j,i$. We must now model the relation between $A$ and $Y$, as well as between $B$ and $X$. In fact, $A_{i,l,t+1}$ (representing agent $i$ being on cell $l$ at timestep $t+1$) must be the sum of $A_{i,l,t}$ (agent $i$ may have been in that cell in the previous timestep and remained stationary) with $\sum_j Y_{ijlt} - \sum_j Y_{iljt}$ (agent $i$'s movements entering or leaving that cell). If the agent remains stationary, the latter part of the sum is equal to $0$. Analogously, a similar relation exists between $B$ and $X$. Formally, for all $i$, $l$, $t$,

\begin{equation}
    \begin{split}
        A_{i,l,t+1} & = A_{i,l,t} + \sum_{j \in V_{1l}} Y_{ijlt} - \sum_{j \in V_{1l}} Y_{iljt},             \\ % player positions are related to their movements
          B_{l,t+1} & = B_{l,t} + \sum_{j \in V_{kl}} X_{jlt} - \sum_{j \in V_{kl}} X_{ljt}.                 \\ % ball positions are related to its movements
    \end{split}
\end{equation}

Our optimization function now differs in the fact that $t$ must be taken into account. This is necessary due to the fact that the ball may remain in the same place for several turns, which counts as movement to the same cell. In other words, reaching the goal $G$ on the second timestep $t$ and waiting there for $50$ turns is equivalent to waiting $50$ turns and then entering the goal. Therefore, our objective functions is now

\begin{equation}
Z = \sum_{t,l \in V_{kG} \setminus G} ( t * X_{lGt} ) .
\end{equation}

We must update the previously described constraints so that the ball enters the goal $G$ only once at any timestep $t$ and leaves the source $S$ at timestep $0$. Our modeling of $B$ dependent on $X$ will ensure that the ball will move among the cells from $S$ to $G$.

\begin{equation}
    \begin{split}
        \sum_{l \in V_{kS}} X_{Sl0} & = 1,                \\ % ball leaves Source once
        \sum_{j \in V_{kG} \setminus G,t} X_{jGt} & = 1,  \\ % ball enters Goal once
    \end{split}
\end{equation}

Finally, we must guarantee that the agents do not overlap and that they carry the ball, kick it to the goal $G$, or pass it at each other. In other words, the amount of agents at node $j$ cannot exceed $1$ and the ball must either be at one of the agent's positions or at the goal $G$. Formally, for all $j$, $t$,

\begin{equation}
    \begin{split}
        \sum_{i} A_{ijt} \leq & 1,                              \\ % only 1 agent per cell
        B_{jt} \leq & \sum_i A_{ijt} + B_{Gt}.                  \\ % ball can only exist at Goal or where there are agents
    \end{split}
\end{equation}


Circuit size for "at least n inputs are true"

From S. Chaudhuri, J. Radhakrishnan. Deterministic Restrictions in Circuit Complexity:

Theorem 6.1: A circuit computing $T_k^n$ with $k \leq n^{1/3}$ has $\Omega(k^2(\ln n)/\ln k)$ gates

Where $T_k^n$ is the boolean function that has the value 1 iff at least $k$ of its inputs have the value 1 (threshold function).


Function that cannot be computed by a Boolean circuit of size $2^n/2n$

We need counting argument here. First thing is, there are $2^{2^{n}}$ many boolean functions, second thing is to count the number of boolean circuits for $k$ size boolean circuit. There are $2^{k^2} \times 3^{k}$ many  boolean circuits of size $k$ (use adjacency matrix ). In your case value of $k =\frac{ 2^n}{2n}$, now you can easily check that

  $$2^{2^{n}} > 2^{k^2} \times 3^{k} $$

So it means there are more number of functions than the total number of boolean circuits. There has to be at least one function that can not be computed by $k$ size circuit ( pigeonhole principle ). One thing to note here that I have proved the existence of such type of boolean circuit but to come up with such type of boolean circuit is quite hard.


Finding The Inverse of The Modulo Operation

I ended up solving my issue, but not in the way I expected. The solution involves the inherent halving of the output string. Using this, one can simply calculate the quotient of dividing x by y and using that as the second alphanumeric character, forming a pair. In the given example, the resulting G would become G1 because the modular arithmetic involved looping over the alphanumeric character array once.

The algorithm is now as follows: x % y = r + (x / y), which is easily reversible by bruteforcing the possible dividends and simply selecting the correct one using the second character in the alphanumeric pair. Thus, this modified algorithm is now reversible and has been proven to work with the example given in the original question.


Probability of randomly designated subsets cover the universe

There is no polynomial-time algorithm that computes an exact solution (i.e. the probability expressed as a ratio of two nonnegative integers $a/b$) to your problem unless $\textbf{P} = \textbf{NP}$.
I will show that such an exact solution would provide a polynomial time algorithm for set-cover.

Let $(U, S \subseteq \mathscr{P}(U), k)$ be an instance of set-cover. Let $m = |S|$.

Let
$$
 \Gamma = \left\{ K \in \mathscr{P}(S) : U =\bigcup_{X \in K} X \right\}
$$

For each $h \in \mathbb{N}$ let:

$$
 \nu_h = |\{K \in \Gamma : |K|=h\}|
$$

Observe that our instance of set-cover is satisfiable if and only if $\nu_k \neq 0$.

Now, let $T$ be a set, constructed as in the problem statement. $T$ covers $U$ if and only if $T \in \Gamma$. Therefore:

$$
\mathbb{Pr}\left[ U =\bigcup_{X \in T} X \right] = \mathbb{Pr}[T \in \Gamma] = \sum_{X\in\Gamma}p^{|X|}(1-p)^{m-|X|} = \sum_{h=0}^m \nu_h p^h(1-p)^{m-h}
$$

The rightmost expression is a polynomial over the ring $\mathbb{Q}[p]$, which means that its coefficients can be found by computing its value at $m-1$ points and applying an algorithm such as the finite differences method.


See "eaters" category.

They can absorbe gliders and spaceships, but I'm not an expert and I don't know if there are "walls" capable of absorbing everything. Perhaps it is a nice subject to investigate! (see the references at the bottom of Wikipedia pages for modern approaches using constraint solvers).

From the lexicon:

:eater Any still life that has the ability to interact with certain patterns without suffering any permanent damage. (If it doesn't suffer even temporary damage then it may be referred to as a rock.) The eater1 is a very common eater, and the term "eater" is often used specifically for this object. Other eaters include eater2, eater3, eater4 and even the humble block. (In fact the block was the first known eater, being found capable of eating beehives from a queen bee.) Another useful eater is shown below, feasting on a glider.


Hint: Add a new vertex to your graph..
Further hint:

...with an edge connecting to each element of $S$.


Information-theoretic limits for a weighing puzzle

You don't need to distinguish n! permutations. You only need to decide whether you have one particular permutation or not.
You start with a set of n! possible permutation. Then you make a measurement, and some permutations in that set are compatible with your measurement, and some are not. So you replace the set of permutations with one that is compatible with your measurement.
For sorting, your measurement is a comparison of two elements. What you need to achieve is that no matter what the outcome is, you are finally left with a set containing one permutation only. To achieve this, you will try to find a comparison that splits your set into two halves that are as close together in size as possible, in case the outcome of the comparison leaves you with the bigger set.
For your problem, you just need to decide whether the permutation (1, 2, 3, ..., n) is in the set of permutations compatible with your measurements or not. You will therefore make a measurement where one of the two possible outcomes means that (1, 2, 3, ..., n) is in your set, and as few other permutations as possible. So you want to split the set as unevenly as possible.
That's what you did. Comparing (1, 2, 3) against 6 means that only twelve permutations including the perfectly ordered one will be compatible with the result: (1, 2, 3) can be ordered in six ways, and (4, 5) can be ordered in two ways. If the comparison is not equal, then there are 708 permutations compatible with that, but that is fine since you have your answer.
Obviously each coin except one must be part of some weighing (if you leave out two coins you can't know if they are in the right order). If you had a limit like "at most four coins can be weighed" that would give you a lower bound. Since you are allowed to weigh all coins in one measurement you'd have to come up with something more clever to find a useful lower bound.


For the first undecidable language $L_1$ you can apply the Rice's theorem:

Theorem (Rice’s Theorem): Let L be a language of the form

$L = \{ \langle M \rangle | L(M)\mbox{ has some property }P\}$,where

P is non-trivial, i.e. there exist at least one machine M such that $\langle M \rangle \in L$, and at least one machine $M$ such that $\langle M \rangle \notin L$.
P is indeed a property of the language of TMs, i.e. whenever $L(M_1) = L(M_2)$,
we have $\langle M_1 \rangle \in L$ if and only if $\langle M_2 \rangle \in L$.

Then L is undecidable.

You can pick a Turing machine that decides $A_0$ and one that decides $\overline{A_0}$, so $L_1$ asserts a nontrivial property of $\langle M \rangle$, and so it is undecidable.

For the second decidable language $L_2$ the machine $M_0$ is fixed (it is not part of the language).
So $L(M_0)$ is regular or it is not regular. If it is not regular then $L_2 = \emptyset$ (trivially decidable). If $L(M_0)$ is regular then there is a DFA $A_{M_0}$ such that $A_{M_0} = L(M_0)$ and the language $L_2$ becomes:

$L_2 = \{ \langle A \rangle | L(A) = L(A_{M_0}) \}$

but the equivalence of two DFAs is decidable, so $L_2$ is decidable.


Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD?

With three steps we are not forced to complete all the steps before continuing interacting with other context around the two initial letters.

In fact, Révész himself answers this question, in his Introduction to Formal Languages at archive.org, with the following example.

  Note that three rules like AB → A'B, A'B → A'D, and A'D → CD are
  not enough to replace the rules AB → CD. For example, if we have the
  rules S → AB, B → DE, AB → CD in the original grammar, then this
  replacement makes the derivation

  S ⇒ AB ⇒ A'B ⇒ A'DE ⇒ CDE

  possible, though CDE is not derivable in the original grammar. Such
  parasitical derivations are often quite difficult to avoid when we are trying
  to transform a grammar into an equivalent one.


Algorithm to solve Turing's "Halting problem"

Can I find a general algorithm to solve the halting problem for some possible program input pairs?

Yes, sure. For example you could write an algorithm that returns "Yes, it terminates" for any program which contains neither loops nor recursion and "No, it does not terminate" for any program that contains a while(true) loop that will definitely be reached and doesn't contain a break statement, and "Dunno" for everything else.

  Can I find a programming language (or languages), where I for every kind of program in this language, it can decide if the program terminates or run forever?

Not if that language is Turing-complete, no.

However there are non-Turing complete languages like for example Coq, Agda or Microsoft Dafny for which the Halting Problem is decidable (and in fact is decided by their respective type systems, making them total languages (i.e. a program that might not terminate will not compile)).


Recurrence Question:T(n) = T(n − √ n) + T( √ n) + θ(n)

The solution is $T(n) = \Theta(n^{3/2})$.

For the lower bound, note that $T(n) \geq T(n-\sqrt{n}) + \Theta(n)$. Iterating this for $\sqrt{n}/2$ steps, the value of the parameter never drops below $n/2$, for a total contribution of $\Omega(n^{3/2})$.

For the upper bound, let us notice first that
$$(n-\sqrt{n})^{3/2} \approx n^{3/2} - \sqrt{n} \frac{d}{dn} n^{3/2} = n^{3/2} - \Theta(n). $$
This allows us to prove the upper bound $T(n) = O(n^{3/2})$ by induction.


The positivity condition is not there just so that "programs terminate", as you put it (what programs?), but to make sure the type is well defined in the first place. The inductive definitions define the smallest type satisfying an equation. That is, we put into the type only those things which are prescribed by the clauses of the definition, and no arbitrary garbage. (Non-normalizing terms count as garbage, and I think that's what you meant when you spoke of terminating programs.)

Let us take a step back and think where the inductive definitions come from. They are solutions to type equations. Here is a type equation:
$$N = \mathtt{unit} + N.$$
What could $N$ be? We might be thinking that it must be the natural numbers, since every element of $N$ is either $\mathtt{inl}(\mathtt{tt})$, which is a fancy way to say "zero", or it is of the form $\mathtt{inr}(n)$ for some $n : N$. But this need not be the case! For example, $N$ could also contain a special element $\infty$ satisfying $\infty = \mathtt{inr}(\infty)$. It could also contain an extra "fake zero" $\mathtt{Z}$, together with its successors $\mathtt{inr}(\mathtt{Z})$, $\mathtt{inr}(\mathtt{inr}(\mathtt{Z}))$, ... There are many solutions to the above equation.

The smallest solution is called the inductive type, and the largest one the coinductive type. I am skipping technicalities about what "smallest" and "largest" mean precisely (they are the "initial algebra" and "final coalgebra", respectively), but I hope you get the point.

In order for us to say that we have a well-defined inductive type, we need to know that the smallest solution to the type equation actually exists. In fact, it does not always exist, sometimes there can be several incomparable solutions, or none at all. The positivity condition in Coq and CIC ensures that a smallest solution exists. It's not the only possible condition one could come up with, and there are variants, but for the purposes of a proof assistant we need something that makes sense computationally, and can actually be verified by a type checker (for instance, it wouldn't do to say that an inductive definition is valid if it defines a $\kappa$-accessible functor for some cardinal $\kappa$, and have the proof checker look for $\kappa$ – hmm, that's an interesting thought).

If we now look at your proposed definition

Inductive t : Type := b : t | c : ((t -> unit) -> unit) -> t.

the question to be asked is: how do you know that the smallest solution exists? Somebody proved that the strict positivity requirement ensures the existence, but your definition falls outside that criterion. You need to provide evidence that there is such a type. The evidence must be a well argued explanation of what the terms of t are that they do not break strong normalization of CIC. You might as well succeed, and there is such a type. The next question then is how do you propose to incorporate your argument into a type checker as a useful algorithm. It's probably not worth the trouble.

Just to show you how problematic these things are, how about the type

Inductive t : Type := c : ((t -> bool) -> bool) -> t.

Is it still totally obvious that there is a smallest solution? We're trying to solve the type equation
$$T = (T \to 2) \to 2.$$
It has no solution in set theory.


Can CNF with an input string be evaluated in logarithmic space?

Yes, you can decide this language in logarithmic space, using the following algorithm:

for each clause in the CNF:

do a linear scan of $w$ to see if one of the literals in the clause is satisfied; if not, reject

if you got through all the clauses without rejecting, accept

What's the space complexity?  Well, there are at most $n$ clauses, so we need at most $\lg n$ bits to store the loop counter to keep track of which clause we're currently on.  We also need to store the current clause; there are at most $n$ variables in the formula, so we need at most $3 (1+\lg n)$ bits to store the clause.  Therefore, we need at most $O(\lg n)$ bits in total of space.

Of course, the running time is not optimal (it is $O(n^2)$ or so), but that doesn't matter, as we're only counting space complexity.


People often use capital letters to represent arrays.  $A$ is a common choice (for the 'a' in 'array'), but by no means mandatory.


What's the average number of transistor switches needed to do an N-bit x N-bit multiply?

I haven't edited my question, but in case others are here: this thesis addresses the question I was intending (https://core.ac.uk/download/pdf/52104064.pdf), finding e.g. 1189 average transitions required for a certain architecture for a 16-bit by 16-bit multiply that's completely random bits.
\


Find a node with maximum distance from query node in a tree

Start from any node and find (say, with a BFS) a farthest node from it; call it $u$. Then start from $u$ and find a farthest node from it; call it $v$. Nodes $u$ and $v$ achieve the absolute maximum distance in the tree.

Now with 2 more BFS, find the distances of all nodes from $u$, and the distances of all nodes from $v$. At this point you are ready to answer the queries: for each queried node $z$, the most distant node is either $u$ or $v$, depending on which has the larger distance. This solves your problem in $O(n + k)$ time.


Efficiently enumerating all "good" strings given the ability to say whether a partial specification can be good

If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. $5^{26}$ is of order $10^{18}$, while the actual number of English words is of order $10^5$. So, depending on your application, simply enumerating all words and checking whether they satisfy the constraints may already be sufficiently efficient.
If we are talking about words of a sufficiently small length, then you can just precompute the answer in advance. I.e. word cut will be in an answer for masks ___, c__, _u_, cu_, etc. For words of length at most 5, it'll result in $\le 2^5 \cdot10^5$ memory, which is of order of few MBs.
If the length is big, then you can split the mask into two parts. For each part, we find all the answers, and then intersect them. For example, we treat mask a_b_c_d_e_ as an intersection of a_b_c|_____ and _____|_d_e_. For both submasks, we find the set of words containing this submask, and then intersect them. If the final answer is small, then, hopefully, the result for at least one of these submasks will be small. You can also try to select the positions to include into each submask randomly.
For even bigger lengths, you can split the mask into more than $2$ parts. However, you can probably use that there are not many very large words and simply enumerate them all.


With regards to (3), there's a fairly simple algorithm to compute large exponents.
exp(a, b) =
  if b is even
     let half = exp(a , b/2)
     return half * half
  else
    return a * exp(a, b-1)

This will be logarithmic in the magnitude of $b$, meaning the number of multiplications is linear in the number of bits used to represent $b$. It's also a very general algorithm: it works for normal exponentiation, matrices, modular arithmetic, etc. The complexity will change depending on the complexity of your multiplication operation.


Is Monotone 3-SAT with exactly 3 distinct variables untractable?

I will try to answer now my own question and would be glad about some feed back concerning the corectness.
Like in the question above discussed and pointed out by Kyle Jones we can reduce arbitrary 3-SAT formulas to monotone 3-SAT formulas.
For example a clause $C=(x_1\vee x_2 \vee \neg x_3)$ can be converted to $C'(x_1\vee x_2 \vee z_3)\wedge (z_3 \vee x_3) \wedge (\neg z_3 \vee \neg x_3)$. One can check if $C$ is satisfiable $C'$ is also satisfiable and if  $C$ is not satisfiable $C'$ is also not satisfiable.
The next step is to convert all the clauses with less than 3 literals to clauses with exactly 3 distinct literals.
Therefore take for example $C_1=(x_1 \vee x_2)$ and transform it to $C_1'=(x_1 \vee x_2 \vee y_1)\wedge (x_1 \vee x_2 \vee y_2) \wedge (x_1 \vee x_2 \vee y_3) \wedge (\neg y_1 \vee \neg y_2 \vee \neg y_3)$ then again if $C_1$ is satisfiable $C_1'$ is also satisfiable and if  $C_1$ is not satisfiable $C_1'$ is also not satisfiable.
The same can be done for the negative case i.e. $C_2=(\neg x_1 \vee \neg x_2)$ can be transformed to $C_2'=(\neg x_1 \vee \neg x_2 \vee \neg u_1)\wedge (\neg x_1 \vee \neg x_2 \vee \neg u_2) \wedge (\neg x_1 \vee \neg x_2 \vee \neg u_3) \wedge ( u_1 \vee u_2 \vee u_3)$
By applying the two transformations one can convert an arbitrary 3-SAT instance to a monotone 3-SAT instance with exactly 3 distinct literals. As can be seen easily above the transformations have polynomial complexity. Therefore since 3-SAT is NP-hard the reduction aswell must be NP-hard.


How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP?

After @YuvalFilmus' hint it turns out the answer lies in this book. The TSP can be used to solve the Hamiltonian Cycle problem by creating a new graph as following. Given $\alpha > 1$ and  a graph $G=\langle V,E \rangle$ we create a new graph $G'=\langle V',E' \rangle$ such that $w(e')= 1$ if $e\in E$, and $w(e')= \alpha n+2$ if $e\notin E$. If $G$ has a Hamiltonian cycle then $G'$ has a tour of length $n$, otherwise each tour has length is at least $(\alpha+1)n + 1$.

Now we run $\alpha$-approximation algorithm for TSP and if the tour computed has cost at most $(\alpha+1)n$ then there is a Hamiltonian cycle in $G$, otherwise there doesn't. If we set $\alpha = O(2^n)$ then we have $O(2^n)$-approximation algorithm. This algorithm runs in $O(f(2^n))$ time for some polynomial $f$, but its time complexity is still polynomial in length of input. This means we would solve the Hamiltonian Cycle problem in polynomial time implying $P=NP$.


Why is the CPU Involved During Keyboard Echo?

Letting the computer see each character as it is typed allows programmers to make the user interface more dynamic.

Back when a serious computer was the size of several upright refrigerators and computers operated on user input a line at a time, terminal input was handled as you described.  You typed a line of text on a terminal which displayed it locally (often on paper).  Only when you pressed the ENTER or RETURN key was the text sent to the mainframe or minicomputer to be processed.

But even back then, the advantage of letting the computer see the user input early was realized by the engineers of the time.  Command completion, where you type the first few letters of a command and the computer fills in the rest, was invented in the mid 1960's.  This feature was copied and improved through the years to where it stands today, available in all modern UNIX shells and under Windows as well.

Allowing the CPU to see each character as it is typed also allows shells to offer command line editing and history features well beyond what a dumb terminal could provide.  A key can allow you to step back through a list of commands you've previously typed, choose one, and then edit it slightly before pressing RETURN to have it executed.  Text can be cut and pasted between command lines, possible because the CPU has access to previous commands while the terminal does not.  Filenames as well as commands can be completed based on partial input, again possible because the CPU has access to the names of files in the filesystem and the terminal does not.


Understanding compression/encoding in linear time

I have checked the code, reread the paper and it seems that algorithm is not performing in $\mathcal O(n)$ in the way you have described.
The recursive calls of finding pairs works in $\mathcal O(n \log n)$ divided by constant if you wish to pack it to the end. In fact the structure underneath keeps pointers to the first occurence of pair, splits the queue of pairs by occurences to make it efficient, but still loglinear. On the other hand by analysing the code written by Ph.D. student of the author I have discovered several tricks - the length of pairs (the original name) is given as parameter (default is 2) and the recurrence is limited by parameter, which can discard further calls (default is about 5 levels), with ability to make only one pass or push to the end. The default code runs in $\mathcal O(n)$, but will not yield optimal compression. There is also switch to prefer memory, time or be neutral.

The paper and the code shows usage of hash-table, which runs only in expected constant time, but the function given works very well with characters. Also the code limits the input length by constant hardcoded.

Changing hashtable to suffix tree and rewritting the part of recurrence into bookkeepping partial pairs might yield better results - I am not sure if this is possible to make it $\mathcal O(n)$, this would be probably a different question.

There is also trick used to keep empty space from traversing - the start of empty block points to the first non-empty character, but this only speeds up traversing, still with loglinear time. The part responsible for this behaviour is replacing pairs by the new character every iteration - keeping only rewrite rules and operating on them would be faster, but still the access to check if new pairs were introduced would require to check rewrite rules against the new ones - in the case we build full binary tree with pairs at the leaves in such way that after replacing pair with new character and concating with the parent we got new pairs at the leaves up to the root - there are $n$ chatacters then $\frac{n}{2}$ pairs, then $\frac{n}{4}$, $\frac{n}{8}$, $\frac{n}{16}$... You see the pattern, there are $2n$ pairs, but according to algorithm description this yelds $\mathcal O(n\log n + n)$ time taking only input traversals.


Hamming distance necessary for detecting d-bit error and for correcting a d-bit error

The first step towards clarifying your confusion is forgetting about the formulas. You should be able to understand this material without looking at the formulas. You should even be able to develop the formulas on your own.

Now to the actual question at hand. Suppose we have a bunch of codewords, and every two are different in at least 10 positions. Suppose I send one codeword on the air, and an adversary corrupts (flips) $x$ bits. I claim that if he flips a small enough number of bits, then the receiver can detect that the adversary modified my codeword. The way she is going to do that is by noticing that what she got wasn't a codeword at all. If $x < 10$ then flipping $x$ bits, the adversary cannot reach another codeword, since by assumption any two codewords differ in at least 10 positions. So if the adversary flips $x < 10$ bits, the receiver will notice that the communication was corrupted on air. That's the meaning of "$d$-bit errors can be detected", where here $d = 9$.

Continuing the same scenario, the receiver isn't really interested in knowing whether some bits were flipped. Rather, she wants to know what the original codeword was. Suppose we can promise her that at most $y$ bits were flipped. When can she recover the original codeword? How is she going to recover the original codeword? Suppose that what she gets is the word $w$. She is going to look for the closest codeword $c$, and guess that the original codeword that was sent was $c$. When can we be sure that she is right?
Suppose that the original codeword was actually $o$. So the distance (number of different positions) from $o$ to $w$ is at most $y$ (since we allowed the adversary to flip at most $y$ bits). As $c$ is the codeword closest to $w$, the distance from $c$ to $w$ is also at most $y$. So the distance from $o$ to $c$ is at most $2y$. Since both $o$ and $c$ are codewords, either they are the same (and we win – the receiver found the original codeword), or $2y \geq 10$, since any two codewords differ by at least 10 positions. As long as $2y < 10$, this cannot happen. Reiterating, if $2y < 10$, then even if the adversary flips up to $y$ bits on air, the receiver can know what the original codeword was by looking for the codeword closest to the word she received. That's the meaning of "$d$-bit errors can be corrected", where here $d = 4$.

More generally, if the minimum distance of the code – the minimum distance between two codewords – is $D$, then the first argument will work as long as $d < D$, and the second as long as $2d < D$. Given $d$, the minimum value of $D$ satisfying $d < D$ is $D = d+1$, and the minimum value of $D$ satisfying $2d < D$ is $D = 2d+1$. That's where the formulas come from. But don't memorize the formulas. Understand where they come from instead.


Value of constants in Big Theta notation

No, the constants $c_1,c_2$ are the same for all values of $n$. If they could depend on $n$ then the definition would be meaningless since $\Theta(g(n))$ would contain all positive functions. Indeed, suppose $f,g$ are two positive functions. Then for all $n$, $$c_1g(n) \leq f(n) \leq c_2g(n) \text{ for } c_1 = c_2 = \frac{f(n)}{g(n)}.$$


Is it correct to use the pinhole camera model to get the mapping of a 3D line to a line in an image?

The assumption is correct, if(f) you project the 3d line into the rectified image. The idea of projecting a 3d-line to a pixel-line is most often used in a stereo setup with two cameras: if the left camera sees a features at a certain pixel, then you know that this object is on a 3d-ray that corresponds to this pixel. If you want to search this object in the right camera's image, you only have to search on the pixel line that corresponds to this 3d-line.
Keywords are here epipolar geometry or epipolar line:
https://www.robots.ox.ac.uk/~vgg/hzbook/hzbook1/HZepipolar.pdf


Why operating system needs interrupt stack, if it has process control block?

The operating system cannot continue using user-accessible memory when it is handling an interrupt, that program may be buggy, malicious, or worse. It may overwrite any part of its address space at any time. That includes the stack.

The stack is often a critical part of the execution of a program, so the operating system has no choice other than to switch to another stack, which the user mode program can't corrupt.

The PCB holds information about a task. When that task is not running, the PCB may hold the context.

There may be two different kinds of context saves, one for switching from one task to another, and one just for when it is preempted by an interrupt. The latter is held on the interrupt stack, which as mentioned is separate from the user mode stack for security and correctness reasons.

Unless there is some microarchitectural reason to have a special stack for interrupts, kernel stacks and interrupt stacks are very similar, only differing in when they are used. The specifics about the stack are implementation details.


Is the closure of P under e-free homomorphisms equal to NP?

As Ryan Williams explains on CSTheory.SE, the answer is probably no: certificates of linear size are probably not enough for NP; some NP problems seems to require certificates of super-linear size.

You can also find some examples of NP-problems that appear to require super-linear certificates over on CSTheory: see Natural NP-complete problems with “large” witnesses and Is the Witness Size of Membership for Every NP Language Already Known?.  Also Problem unsolvable in 2o(n) on inputs with n bits, assuming ETH? might be relevant as well.


Efficient way to reduce a binomial coefficient as a fraction

You store the numbers n-k+1 to n in an array.

Then for each prime number p ≤ k: Find which power of p is a factor of k! (Thats k/p + k/p^2 + k/p^3 ... ) Then remove that power from the array: Find the first number divisible by p (that would be the number at index 0 if n-k+1 is divisible by p, otherwise at index p - ((n-k+1) modulo p)). That number is divisible by p, possible by p^2 etc., and the next number divisible by p is at the index p higher).

You are now left with an array of k numbers that you need to multiply.


What does it mean to say that a language is "effectively closed" under an operation?

"Effectively closed" means that the family is closed under the operation, and that the closure can be computed by giving an automaton/grammar for it (if the original languages are also given in such an effective representation). E.g., given a finite state automaton, we can actually find an automaton for the complement.

Then it is a natural question, whether there are examples of closure properties that are not effective. I know one right now. For a regular language $R$ and any language $L$ the quotient $R/L$ is again regular. There is no effective way to construct a FSA for that quotient if $L$ is e.g. recursively enumarable.


Is deep learning appropriate to approximate dynamic programming problems?

A good start would be to understand what reinforcement learning is; and identify which problems are reinforcement learning problems and which aren't.  Deep reinforcement learning is only relevant if you have a reinforcement learning problem; otherwise, it's almost certainly not relevant.  Among other things, reinforcement learning deals with a stateful system.  You don't seem to have a stateful system so it's not clear to me why you think reinforcement learning would be relevant.

Since you haven't told us what the problem is, it's hard to imagine how we can tell you how to solve it; all I can share is general principles.  In general, deep reinforcement learning isn't magic that you use whenever a problem is too hard for normal methods; it is useful for a specific purpose, and I don't see any reason to expect it to be effective or applicable here.


Is there a generic algorithm for translating equational rules into corresponding data structures?

It sounds like what you are asking for is, for a given equational system $\cal E$, to give a canonical representation for equivalence classes modulo $\cal E$.

Indeed, if your signature is the binary operation $\_\cdot\_$, and your equation is
$$ (x\cdot y)\cdot z=x\cdot(y\cdot z)$$

then you can represent any element as $a_1\cdot(a_2\cdot(\ldots\cdot a_n)\ldots)$ (where the $a_i$) are atoms. As Derek Elkins points out, a good way to do this is to apply Knuth-Bendix completion to $\cal E$, (possibly) obtaining a rewrite system $\cal R$ that is confluent and terminating and computes, for each term $t$, a unique element that is a representative of $t$'s equivalence class under $\cal E$.

Now it is useful to note that in this case, the set of canonical forms happens to be isomorphic to the data types of lists of atoms. The fact that elements of an algebraic datatype captures the equivalence classes is not obvious, and is not true in general: if you add commutativity, that is the equation
$$ x\cdot y = y\cdot x$$
then it's clear that there is no algebraic (first-order) datatype that captures exactly the normal forms, as this is isomorphic to sorted lists of atoms.

A reasonable question is to ask whether there is always such a data structure using dependent types. In particular, there is a version of sorted list using dependent types, namely:

data SortedList =
  Nil : SortedList
  Cons : forall x:Atom, forall l:SortedList , x <= min l -> SortedList

taking inspiration from this agda code. Note that min needs to be defined on SortedList, making this an inductive-recursive definition, but I'm pretty sure this can be avoided with a little more messiness (say, embedding list into sorted list).

I think the question needs to be made more precise though, because there is a type in extensional dependent type theory such that each element of that type represents exactly one equivalence class: namely, the type of all equivalence classes! It can be defined by

$$ \mathrm{Q}_E:=\{y|\exists x, \overline{x} = y\}$$
where $\overline{x}$ is defined by:
$$\overline{x}=\{z| z=_E x\} $$

In general, quotient types are a tricky subject in type theory though, especially without sufficient extensionality, see e.g. Pragmatic Quotient Types by Cyril Cohen.

In conclusion:

In the naive version of your question, the answer is that it is impossible to associate an inductive data type to an equational theory such that each element of the type represents a unique class.
It is sometimes possible to compute a rewrite system which computes a unique representative of that class if the algorithm terminates and succeeds.
When allowing for dependent types, the question becomes more complex and is, I believe, still somewhat open, with some progress.


Subset sum exponential solution - how does the sorting work?

The idea is that two sorted lists of length $n$ can be merged into one sorted list of length $2n$ in time $O(n)$. This is a standard procedure used in the mergesort algorithm. Given a list of integers $x_1,\ldots,x_m$, you proceed as follows:

Start with $A_0 = 0$.
Merge $A_0$ and $A_0 + x_1$ into $A_1$.
Merge $A_1$ and $A_1 + x_2$ into $A_2$.
...
Merge $A_{m-1}$ and $A_{m-1} + x_m$ into $A_m$.
Output $A_m$.

Here $A_k + x_{k+1}$ is formed by adding $x_{k+1}$ to all elements of $A_k$, preserving the order.

Since $A_k$ has length $2^k$, the total running time is
$$
O(|A_0| + |A_1| + \cdots + |A_{m-1}|) = O(1 + 2 + \cdots + 2^{m-1}) = O(2^m).
$$


Hint : Consider  $G '=(V'=V \cup\{w_i|i\in [1,|V|]\},E'=E\cup\{(w_i,v)|v \in V , i\in [1,|V|]\})$ and $k'=|V|^2+k $

Consider a partition of V' in 3 parts, call $P $ the one with the smallest number of nodes in  $V $.

Note that by putting a w in P , if it were not in it, you increase the number of edges in your 3cut.

Then, note that if all the ws are in the same part, then removing a node of V from that part increases the number of edges in your 3cut.


Why there are no approximation algorithms for SAT and other decision problems?

Approximation algorithms are only for optimization problems, not for decision problems.

Why don't we define the approximation ratio to be the fraction of mistakes an algorithm makes, when trying to solve some decision problem?  Because "the approximation ratio" is a term with a well-defined, standard meaning, one that means something else, and it would be confusing to use the same term for two different things.

OK, could we define some other ratio (let's call it something else -- e.g., "the det-ratio") that quantifies the number of mistakes an algorithm makes, for some decision problem?  Well, it's not clear how to do that.  What would be the denominator for that fraction?  Or, to put it another way: there are going to be an infinite number of problem instances, and for some of them the algorithm will give the right answer and others it will give the wrong answer, so you end up with a ratio that is "something divided by infinity", and that ends up being meaningless or not defined.

Alternatively, we could define $r_n$ to be the fraction of mistakes the algorithm mistakes, on problem instances of size $n$.  Then, we could compute the limit of $r_n$ as $n \to \infty$, if such a limit exists.  This would be well-defined (if the limit exists).  However, in most cases, this might not be terribly useful.  In particular, it implicitly assumes a uniform distribution on problem instances.  However, in the real world, the actual distribution on problem instances may not be uniform -- it is often very far from uniform.  Consequently, the number you get in this way is often not as useful as you might hope: it often gives a misleading impression of how good the algorithm is.

To learn more about how people deal with intractability (NP-hardness), take a look at Dealing with intractability: NP-complete problems.


A version of the longest simple cycle problem - NP-completeness reduction proof

In order to prove NP-completeness of a given problem $\Pi$, it is enough to prove that $\Pi \in$ NP and that there exists a polynomial time reduction from any NP-complete problem $\Pi^*$ to $\Pi$.  The reduction must take instances of $\Pi^*$ and return instances of $\Pi$, in polynomial time, such that the answer is the same in both $\Pi^*$ and $\Pi$.

A suitable reduction from Hamiltonian Circuit has been proposed in a comment to the question: just add enough (that is $n$) isolated vertices to the graph.


How do you find all integers in a sorted array of size n that appear n/k times?

Let's start with the case $k = 2$, and assume that the algorithm is comparison-based.
I claim that any algorithm that finds even a single element appearing $n/2$ times must know an index $i$ such that $A[i+1] = A[i+n/2]$. Indeed, suppose that this is not the case, and let us assume for simplicity that the entries of $A$ are real numbers. Let us say that the algorithm known the following values:
$$
A[i_1] = \cdots = A[j_1] < A[i_2] =\cdots = A[j_2] < \cdots
$$
It is consistent with the algorithm's knowledge that $A[i_1-1] < A[i_1] < A[j_1+1]$ and so on, and with a little effort we can arrange that there is no element appearing $n/2$ times.
Consider now the $n/2+1$ arrays of the following form: there is a run of $n/2$ many $0$s starting at some position $j \in \{1,\ldots,n/2+1\}$, and the rest of the elements are unique. In each such array, there is a unique choice for the index $i$ mentioned above. Thus the decision tree representing the algorithm has at least $n/2+1$ leaves, and so it must have depth $\Omega(\log n)$.

In the general case, the algorithm should know an index $i$ such that $A[i+1] = A[i+n/k]$ for each element which is output. We can partition the array into $k/2$ parts of size $2n/k$, and consider $(n/k+1)^k$ examples as before, where the $r$th element appearing $n/k$ times is in the $r$th part. This gives a lower bound of $\Omega(k\log(n/k))$, matching your upper bound for nearly all values of $k$.
(The algorithms can probably be slighly improved to give a matching upper bound.)


$A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$?

I think you've confused the direction of the reductions. A reduction from $A$ to $B$ means that you could solve $A$ efficiently if you had an efficient way of solving $B$. It's certainly true that you could determine membership of a finite language efficiently if you could solve some NP-complete problem. After all, you can determine membership of a finite language efficiently already, without needing to solve, say, travelling salesman.

On the other hand, it would be surprising if there was a polynomial-time reduction from some NP-complete problem to the problem of determining membership of a finite language. That would be saying, "If I could determine membership of this finite language efficiently, I could solve every problem in NP efficiently."

In case you weren't confused about which way reductions go, here's a concrete reduction from the language $\mathcal{L} = \{\mathrm{elimination}, \mathrm{computer}, \mathrm{science}\}$ to Boolean satisfiability.  We will define a polynomial-time computable function $f$ from strings $\{a, \dots, z\}^*$ to Boolean formulae such that $f(w)$ is satisfiable if, and only if, $w\in \mathcal{L}$.

if w = "elimination" or w = "computer" or w = "science"
    return "X"
else
    return "X∧¬X"


Log-Space Reduction $CO-2Col \le_L USTCON$

Hint: Extend the input graph to a connected graph which is bipartite iff the original graph is bipartite.

If the original graph is not bipartite, then the new graph will a fortiori not be bipartite. The more difficult direction is ensuring that when the original is bipartite, the new edges do not render it non-bipartite. This property is satisfied as long as the edges that you introduce do not close an odd cycle.

Further hint: Take $n$ copies of your original graph (where $n$ is the number of vertices), and add a new vertex $s$. Connect $s$ to the $i$th vertex in the $i$th copy.


Prove that if $p_1 \times p_2$ is positive, then $p_1$ is clockwise from $p_2$?

In two-dimensional space, $p_1 \times p_2$ is equal to $|p_1||p_2|\sin\theta$, where $\theta$ is the angle from $p_1$ to $p_2$. Depending which textbook you're using, this is probably the definition of the two-dimensional cross product—I'm not sure what definition Introduction to Algorithms uses.

$|p_1|$ and $|p_2|$ both have to be non-negative (by the definition of vector magnitude), so if neither of them is zero, the sign of the whole expression will be the sign of $\sin\theta$.

Now, how do we define "clockwise"? The easiest definition I know is is, $p_1$ is clockwise from $p_2$ if the angle(*) from $p_1$ to $p_2$ is less than 180 degrees. Try a few examples and you'll see how this definition works—remember that angles are traditionally measured with counter-clockwise being positive.

Now, we know that if $p_1 \times p_2$ is positive, then $\sin\theta$ must be positive. And if $\sin\theta$ is positive, then $\theta$ must be less than 180 degrees(*). So by the definition of clockwise, $p_1$ is clockwise from $p_2$.

(*) I'm assuming without loss of generality that all angles are positive and less than 360 degrees.


First, a note on notation: $L(M)$ is a language which is a set. Languages don't accept or reject, Turing machines do. You can either say "$\epsilon \in L(M)$" or "$M$ accepts $\epsilon$".

There are many Turing machines in this language that don't meet your description. For example, imagine a machine that upon reading a blank goes and writes, say, 111 and then accepts. The initial state does not need to have a transition to an accept state on a blank symbol in order to belong in this language.

Here's another perspective on why this language is undecidable using Kleene’s Recursion Theorem. Imagine that there is some decider $D$ that, given the description of a TM $\langle M \rangle$, $D$ accepts if $M$ accepts $\epsilon$ and rejects otherwise. Now create a Turing machine with the following behavior:

Get my own description <M> and then run D on <M>.
If D accepts <M>:
   If input is empty, reject. Otherwise accept.
Else:
   If input is empty, accept. Otherwise reject.

The existence of this decider allows us to create the above Turing machine which is a contradiction. Essentially, if the decider says the Turing machine is supposed to accept the empty string, it then goes and rejects and if it's supposed to reject, it then goes and accepts. This idea of being able to use self-reference and ask "What am I about to do?" and then doing the opposite shows that no single machine can predict behavior of all others.


Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them

The problem was considered by Kahn and Saks in their paper Balancing poset extensions. Earlier related works are Fredman, How good is the information theory bound in sorting? and Linial, The information-theoretic bound is good for merging.

Kahn and Saks showed that partially sorted lists can be sorted in $O(\log M)$, where $M$ is the number of possible orderings consistent with the partial order. I'm not sure that their algorithm is efficient, though. The best constant in the big O is the subject of the 1/3–2/3 conjecture.


Approximability of the edge-disjoint shortest paths problem

Below, we will assume there is exactly one shortest path between every pair of vertices. The following will also work for the case where $O(\log n)$ pairs of vertices have $O(1)$ shortest paths between them.

For each pair $\{s_i , t_i\}$ let the shortest path be $P_i$, $\forall i \in \{0,1\ldots k\}$. The shortest path can be found in polynomial time. Let us number the edges $e_1, e_2, \ldots e_q$. Let the maximum number of pairs $\{s_i , t_i\}$ for which there exist disjoint-shortest paths be $\text{OPT}$.

Now, we reduce this problem to an optimization problem.

Define a matrix $A_{k\times q}$ such that $A_{ij} = 1 \text{ if } e_j \in P_i$.

$$
\text{OPT} = \max \sum_{i=1}^k x_i \quad
\\
\text{s.t } Ax \leq \mathbf{1}_{n\times 1} \\
x \in \{0,1\}
$$

Let the optimal fractional solution for the above problem be $\text{OPT}_{\text{LP}}$ and $\text{OPT}_{\text{LP}} \geq \text{OPT}$. The above LP has an integrality gap of $O(\log k)$. Therefore, $O(\log k) \cdot \text{OPT}_{\text{IP}} \geq \text{OPT}_{\text{LP}}$. Thus $ O(\log k) \cdot \text{OPT}_{\text{IP}} \geq \text{OPT}$. Hence we obtain a $O(\log k)$ approximation algorithm.

The proof for the integrality gap result can be found in Vazirani's "Approximation Algorithms", chapter 20. Multicut in General Graphs.


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

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


Estimating run time in the absence of knowledge

No, you can't make any well-justified estimate, if you truly have no knowledge.

In practice, it's rarely that case that we have zero knowledge.  Instead, we might have some idea what the distribution of total computation time will look like.  That gives you a prior.  In other words, before you start the computation, suppose I asked you for your guess at the probability distribution of what the total computation time will be.  What probability distribution would you choose?  The result is a prior.

If you have a prior, then you can compute an estimate for the remaining run time and quantify the uncertainty, using Bayesian analysis.  Let $p(x)$ denote the prior probability that the total computation time is $x$; in other words, before you start running it and before you make any observation, $p(x)$ is your estimate of the probability that it will take $x$ seconds to terminate.

Now we make an observation, and we want to update our estimate of the probability.  We observe that the computation has run for $y$ seconds without terminating yet.  This implies that, whatever the true value of $x$ will turn out to be, it will be at least $y$.  Using Bayes' theorem we obtain

$$\begin{align*}
p(x|y) &= {p(y|x) p(x) \over p(y)}\\
 &= {p(y|x) p(x) \over \int_0^\infty p(y|x) p(x) \; dx}
\end{align*}$$

We notice that we're going to need to know the distribution $p(y|x)$.  This helps us realize that the problem isn't well-stated yet: you haven't told us how you would decide when to make the observation.

Suppose that we decide in advance, before starting the computation, that we're going to wait $y_0$ seconds and then check whether it has halted or not.  Thus there are two possible outcomes of the observation: "already halted" (finished in $\le y_0$ seconds) or "hasn't halted yet" (will take a total of $>y_0$ seconds to finish).  Let's denote those by the outcomes "A" vs "H", so we'll say $y=A$ in the former and $y=H$ in the latter.  Then we find that $p(y|x)$ has the following form: $p(A|x) = 1$ if $x \le y_0$, else $p(A|x)=0$; and the reverse for $p(H|x)$.  Plugging into the formulas above, we obtain

$$\begin{align*}
p(x|A) &= {p(A|x) p(x) \over \int_0^{y_0} p(x) \; dx}\\
p(x|H) &= {p(H|x) p(x) \over \int_{y_0}^\infty p(x) \; dx}
\end{align*}$$

When $x \le y_0$, we have $p(x|H)=0$ (naturally).  When $y_0 < x < \infty$, we see that $p(x|H) = p(x)/q$, where $q = \int_{y_0}^\infty p(x) \; dx$ is the prior probability that $x$ falls in the range $y_0 < x < \infty$.  Here $q$ is a constant that depends on the prior probability; you can think of it as a normalization constant to ensure that $p(x|H)$ is a probability distribution (it integrates to one).

This gives you the posterior distribution for $x$, after running the experiment (starting up the computation and after $y_0$ seconds checking to see whether it has finished yet) and making the observation (that it hasn't finished yet).  From the posterior distribution, you can make estimates for the total running time.  For instance, one reasonable way to make an estimate is to compute the expected value of this posterior distribution.  In this way we obtain

$$\mathbb{E}(x|H) = \int_0^\infty x p(x|H) \; dx = {\int_{y_0}^\infty x p(x) \; dx \over \int_{y_0}^\infty p(x) \; dx}.$$

You can also summarize the uncertainty in  your estimate using a 95% credible interval.

As you can see, all of this machinery requires that we have a prior for the total running time.  Selection of the prior isn't something math can give you; instead, it needs to reflect your domain knowledge and expectations.  Probably you have some ideas for how likely it is that the computation will take a certain amount of time.  For instance, maybe it's common for computations to take anywhere from 1ms to 1 day, but it's rare to run across computations that take (say) 10000 hours -- usually they'll either complete much earlier, or (occasionally) they'll take much longer, but 10000 hours is a lot less likely outcome than 1 hour.   So, constructing a prior is the (subjective) process of quantifying that knowledge you already have.  Alternatively, the choice of prior might be informed by data, if you collect a data set of how long other computations have taken to complete and use that to fit some kind of distribution to them.

Once you've chosen a prior, then you can use the mathematics shown above to estimate how long the running time will turn out to be, in a methodologically sound way.


The polynomial algorithm for "classical" graph is based on a maximum matching algorithm completed with the isolated nodes. 3-dimensional matching is known to be NP-complete (https://en.wikipedia.org/wiki/3-dimensional_matching). This is a case of minimal edge cover for hypergraph. Thus the answer is no.


The communication complexity of non-equality

The protocol gives you a covering of the zeroes using $2n$ rectangles $R_{i,b} = X_{i,b} \times Y_{i,1-b}$, where $X_{i,b}$ (or $Y_{i,b}$) is the set of words whose $i$th bit equals $b$.


Number of Solutions for Brute Force Algorithm of Travelling Salesperson Problem

In the classic variant of the Travelling Salesperson Problem, the distance from X to Y is the same as the distance from Y to X for any two locations X and Y. Hence, as you noticed, an algorithm does not need to distinguish between the two solutions A, B, C, D and A, D, C, B. However, whether a brute force algorithm considers both solutions or not would depend on how exactly it is implemented. Some will and some won't. It is not too much of a waste to consider them both -- after all, it only takes twice the time. And it may be easier to program the algorithm that way.

There is also a so-called asymmetric variant of the Travelling Salesperson Problem where the cost of moving from X to Y is not necessarily the same as the cost of moving from Y to X. Note that in this case, the two solutions A, B, C, D and A, D, C, B are not "essentially the same" anymore and it is important to consider them both.


What can be the time complexity of an algorithm that calculates the weights of the nodes in a graph?

for i in V:
    weight(i) = 0
for e=(i,j) in E:
    weight(i) = weight(i) + weight(e)
    weight(j) = weight(j) + weight(e)


Find optimal local alignment of two strings with restrictions

Compute the optimal local alignment score OPT of both strings in $O(mn)$ time and $O(n)$ space by maintaining just a single row of the DP matrix. (Since we are only computing the score and don't need to perform traceback to build the full solution, we don't need to keep the full DP matrix.) As you do so, keep track of the highest cell value seen so far, as well as a list of the coordinates $(i, j)$ of cells having this value. Whenever a new maximum is seen, clear the list and update the maximum. Whenever a cell $\ge$ the current maximum is seen (including in the case where we just saw a new maximum), add the coordinates of the current cell to the list. At the end, we have a list of endpoints of all optimal local alignments; by assumption, there are at most $r$ of these.
For each entry $(i, j)$ in the list:

Set $R1$ to the reverse of the substring $S1[i-q+1..i]$, and $R2$ to the reverse of $S2[j-q+1..j]$.
Perform optimal global alignment of $R1$ and $R2$ in $O(q^2)$ time, maintaining the full $O(q^2)$ DP matrix this time.
Search for the highest entry in the matrix (also $O(q^2)$ time; or you can perform this during the previous step).
If this entry is OPT, we have found a solution: Trace back towards the top-left corner from this cell to find the full solution, reverse it, and output it, and stop.

By assumption, at least one of the alignments performed in the previous step reaches a score of OPT. (Note that reversing both strings does not change the score of an alignment.)
Step 2 iterates at most $r$ times, and does $O(q^2)$ work each time, using at most $O(q^2)$ space, so overall the time and space bounds are met.
(A simpler way, that avoids reversing strings, would be to simply perform local alignments of the length-$q$ substrings, but the restrictions appear to forbid this.)


Fine-grained complexity of 3-CNF formula evaluation

Yes, you are correct.  Your analysis is fine.  It takes linear time.

It's also easy to see that it's not possible to do better than linear time: any algorithm will have to read the entire input (in the worst case), which itself takes linear time.


First Order Logic, First Order Logic + Recurrence and SQL

Yes, FP will be first-order fixed-point logic.

Data complexity is the maximum complexity of the problem of evaluating a fixed formula of the logic on a database, as a function of the size of the database.  Expression complexity (also known as formula complexity) is the complexity of evaluating a formula on a fixed database, as a function of the formula size (e.g., its length as a string of characters).  Combined complexity, which isn't mentioned in your table, is the complexity of evaluating a formula on a database as a function of the size of those two things.

The expression complexity of first-order logic is high because, for example, a formula $\forall x_1\dots \forall x_k$ requires time $n^k$ to evaluate on a database of size $n$, so a formula of length $\ell$ can take time $n^\ell$, which is an exponential function of $\ell$ when $n$ is treated as a fixed constant.  However, we can do this in polynomial space, since all we need to do is loop through potential values of variables and that requires storing just one value per variable.


Find the computational complexity of the given program

You can analyze using master theorem:
$$T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lceil\frac{n}{2}\rceil) + 1$$

As we can suppose $n = 2^k$ and there is no a difference in the asymptotic complexity, We can say $T(n) = 2T(\frac{n}{2})+ 1$.

Hence, from master theorem we can say $T(n) = \Theta(n)$.


It's not quite as simple. Calls to oracle have a "magic" quality of taking only one unit of time. Even if NL can simulate the oracle calls, these simulated invocations of the oracle can take more resources than is needed by the oracle machine. To prove these classes equal you need to prove that calls to the oracle do not improve performance in the computational complexity sense because producing the input to the oracle already requires sufficient resources that the oracle machine cannot use this "magic" to get improved performance.


Solving a maze with DFS vs "wall following"

Try it on some simple examples.  You'll quickly see why wall following is not sufficient.


Distribution of beans in jars to k members

If this is a practical problem, it can be solved using integer linear programming (ILP).

We'll introduce three kinds of integer variables:

$x_{i,j}$ counts the number of beans from jar $i$ that are given to child $j$.
$y_{i,j}$ is 1 if child $j$ gets any beans from jar $i$, or 0 otherwise.
$z_i$ is the number of children who get at least one bean from jar $i$.

Then we'll add some constraints to enforce the requirements in the question:

$\lfloor B/C \rfloor \le \sum_i x_{i,j} \le  \lceil B/C \rceil$ where $B$ is the total number of beans across all the jars.  This ensures that each child receives the same number of beans.
$0 \le x_{i,j} \le B_i y_{i,j}$, where $B_i$ is the number of beans in jar $i$, and $0 \le y_{i,j} \le x_{i,j}$.  This ensures that $x_{i,j}$ and $y_{i,j}$ are consistent with each other.
$\sum_j x_{i,j} \le B_i$.  This ensures that you don't give out more beans from jar $i$ than are available.
$z_i = \sum_j y_{i,j}$.

Finally, the objective function is the average of the $z_i$'s, i.e., $\frac{1}{N} \sum_i z_i$.  We feed this to an integer linear programming solver and ask it to minimize the objective function, subject to the constraints above.

The worst-case running time of ILP solvers is exponential time, but in practice they are sometimes much more efficient than you might think.  If you have $N,C < 50$, I suspect this might be efficient enough to work in practice.  The only way to find out for sure is to try it.


Set combination data structure (And storage complexity)

Question 1:  The storage complexity of a map for holding these values is $\Theta(m)$, where $m$ is the number of entries in the map, assuming we don't count the space to store the sets themselves, and assuming we store them in a hash table (or similar data structure).

This doesn't include the space to store the sets in the keys, as those presumably already exist.  If you want to include that space as well in your estimate of the space complexity, then we need at most $\Theta(m)$ space for the map, plus $\Theta(mk)$ space to hold the sets (assuming each set contains $k$ elements), for a total of $\Theta(mk)$ space.  I am assuming that each element of $S$ can be stored in a single word ($\Theta(1)$ space), e.g., that $n \le 2^{64}$.  If $n$ is huge, so that an element of $S$ cannot be stored in a single word, a better estimate of the total space usage is $\Theta(mk \lg n)$, since it takes $\Theta(\lg n)$ bits to store a single element of $S$, each subset of $k$ elements takes $\Theta(k \lg n)$ bits, and there are $m$ entries in the map, each of which requires $\Theta(k \lg n)$ bits to store it.

The number of unique subsets of size $k$, out of a universe of $n$ items, is ${n \choose k}$.  Therefore, if you know that the keys are subsets of size $k$, you know that $m \le {n \choose k}$.  But you mentioned in the question that the number of entries in the map is less than all possible subsets of size $k$, so this isn't helpful.

Question 2: Yes, a hash table would be an efficient data structure to store these elements.  There's a straightforward way to define a hash function on subsets of $S$, so you can use that to build a hash table.  A hash table achieves the space complexities listed above.


Solve Travelling Salesman once you know the distance of the shortest possible route

You try to find a tour of length ≤ K. What would likely happen: If K is very large then a tour is easy to find. If K is very small then it is easy to prove that a tour doesn't exist. The closer you move K to the critical point (where a tour of length K exists, but K-1 doesn't exist), the harder it will be to either find a tour or prove it doesn't exist. You don't beat NP-completeness that way.

And actually, since NP-completeness is about decision problems (problems with a yes/no answer), that's what the travelling salesman problem actually is: Deciding whether or not there is a tour of length K or ≤ K.


Independent set on cubic triangle-free graphs

Let's start by proving that the maximum independent set is of size at most $|V|/2$. Let $I$ be an independent set. For each vertex $v$, let $\alpha(v)$ be the number of its neighbors in $I$. If $\alpha(v) \geq 1$, then we know that $v \notin I$. Since the graph is cubic, $\sum_v \alpha(v) = 3|I|$. Since $\alpha(v) \leq 3$, the number of vertices such that $\alpha(v) \geq 1$ is at least $|I|$. Hence $|I| \leq |V|/2$.

When can we have equality? We must have $\alpha(v) \in \{0,3\}$, so for each vertex not in $I$, all its neighbors must be in $I$. The converse is also true - for each vertex in $I$, all its neighbors are not in $I$. In other words, the graph must be bipartite. This can be checked in polynomial time.


What is the optimal way to find unique combinations of N sets of integers

This may be wrong
I don't follow the multiple set of the set input part of question

Have a loop for each N

Assume N = 3
L is length of array A

for(i = 0; i < L-2; i++)
    for(j = i + 1; j < L-1; j++)
        for(k = j + 1; k < L; k++)
            A[i], A[j], A[k]

I write poker software and this matches the number of combinations


Can someone give me the definition of #Monotone-2SAT?

Satisfiability problems are about making the formula true, not necessarily the variables. Counting satisfiability problems ask how many different assignments to the variables make the formula true.

In $\#\text{Monotone-2SAT}$, the formula is in 2-CNF (conjunctive normal form with at most two literals per clause) and is monotone (there are no negations). So, certainly, making all the variables true satisfies the formula, but there are plenty of other ways.  Just consider the formula $x\lor y$, which is monotone and in 2-CNF. It has three satisfying assignments.


Does there exist a travelling salesmen generating algorithm?

For posterity and because I never received any answers in the end: my best guess is $\forall x_0 \in [0,1]^2$ was to pick any point $x_1 \in [0,1]^2$, then generate a second point $x_2$ such that the interior angle between the line between $x_0$ and $x_1$ is greater than 90$^{\circ}$ and less than 180$^{\circ}$.  Now I can see two paths forward, one is to make a sort of quasi convex structure (obviously not every solution) by alternating whether the angles are interior or exterior and staying within the bounds. The solution is then $x_{0,...,n}$ for the minimum path.

The second possibility would be to put restrictions on the distance from the last point to the next point, (say halving each time) and again requiring the angle to be constrained, but perhaps this time we can loosen the constraint to greater than 90$^{\circ}$ and less than 270$^{\circ}$ and just require that we cannot cross a line we've already made. I can't guarantee this algorithm will always generate the correct solution, however I can guarantee that it won't generate all points in $[0,1]^2$, so the question remains unfortunately unanswered.

And for the PS in my original question: this might be a good place to get started for those looking.


Your claim is incorrect (which might make it really hard to prove...)
Indeed, as you describe, you can have a full binary tree of height $O(n)$: Let every right child be a leaf, and every left child have 2 children, until some level in which it has two leaf-children.

It holds that $x-1\in \theta(2x-1)$, and in particular, $x-1\in \omega(\log(2x-1))$, so $H\notin O(\log N)$.


Multiprocessor Scheduling is NP-Complete

The deadline is maximum time a single processor can take to complete its tasks (the subset allocated to that processor) where as you are considering deadline as the total of each processor's time.

Let's say there are 6 tasks each with 1 unit of time. Then your example of taking deadline by half of total time of all tasks become 6/2 = 3. Now comes the number of processors which you take to be 2. The task now is to divide the 6 tasks into 2 groups such that the total time of each of the 2 groups is less than or equal to deadline. You cannot compare the sum of total time of each group time with the deadline as the deadline is about the maximum time a single group can take.

In terms of showing that the problem is NP-Complete, I guess you will have to show a reduction of your problem to any of the known NP-Complete problems. Intuitively, I think that this problem can be reduced to a form of subset sum problem which is NP-Complete.


Clarification in the proof for the Bellamn-Ford algorithm

The claim you are trying to prove by induction is wrong, and I believe this is exactly the source of your confusion.

  The correct claim is the following: Consider the values of
  $\text{dist}[\cdot]$ computed at the end of the $k$-th iteration of
  Bellman-Ford. For any vertex $u$, let $d^{(k)}_u$ be the length of the
  shortest path from $s$ to $u$ that uses at most $k$ edges (if no such path exists then $d^{(k)}_u = +\infty$). It holds
  that $\text{dist}[u]\le d^{(k)}_u$.

Notice the $\le$ sign!

The above claim implies that, after the $(n-1)$-th iteration all distances stored in $\text{dist}[\cdot]$ are smaller than or equal to the true distances in the graph.

Clearly, it also holds that all the distances stored in $\text{dist}[\cdot]$ are larger than or equal to the true distances in the graph (since every time you a distance is updated, the new distance is always the length of some path from $s$).

Combining the previous two properties, you can conclude that $\text{dist}[\cdot]$ stores the exact distances from $s$, i.e., that the Bellman-Ford algorithm is correct.

Let me prove my claim formally. To avoid confusion this is the pseudocode of the Bellman-Ford algorithm I will be using:

Bellman-Ford(G=(V,E; w), s):
  For u in V:
    dist[u]=+infinity

  dist[s]=0
  For k=1,..., n-1:
    For (v,u) in E:
      dist[u] = min(dist[u], dist[v] + w(v,u))

The proof is by induction on $k=0, \dots, n-1$ (where the end of the $0$-th iteration corresponds to the state of the algorithm just before the first iteration of the outer for loop).

The base case is $k=0$. There is only one vertex $u$ such that the path from $s$ to $u$ uses $k=0$ edges, namely $u=s$. The claim holds for $s$ since $\text{dist}[s] = 0 = d_s^{u}$. For $u \neq s$, the claim holds since $\text{dist}[u] = +\infty = d_u^{(k)}$.

Suppose now that the claim holds for $k-1 \ge 0$. We will prove that it also holds for $k$. Consider any vertex $u \in V$, let $P$ be the shortest path from $s$ to $u$ that uses at most $k$ edges, let $w(P)$ be the (weighted) length of $P$, and let $|P|$ denote the number of edges of $P$. We distinguish two cases:

If $|P| < k$ then $d_u^{(k)} = d_u^{(k-1)}$ and, by inductive hypothesis, at the end of the $(k-1)$-th iteration of the outer for loop we had $\text{dist}[u] \le d_u^{(k-1)} = d_u^{(k)}$. The claim follows since the values of $\text{dist}[\cdot]$ never increase during the execution of the algorithm.

If $|P|=k$ then $|P| \ge 1$. Let $(v,u)$ be the last edge of $P$ and let $P'$ be the subpath of $P$ from $s$ to $v$.
Let $\delta$ be the value of $\text{dist}[v]$ at the end of the $(k-1)$-th iteration of the outer for loop.
By the suboptimality of shortest paths we know that the (weighted) length $w(P')$ of $P'$ is exactly $d_v^{(k-1)}$. Moreover, the inductive hypothesis ensures that $\delta \le d_v^{(k-1)}$.
Consider the situation at end of the iteration of the inner for loop that considers edge $(v,u)$, during the $k$-th iteration of the outer for loop. Since values of $\text{dist}[\cdot]$ never increase, we must have:
$$
\begin{align*}
\text{dist}[u] &\le \text{dist}[v] + w(v,u) \\
&\le \delta + w(v,u) \\
&\le d_v^{(k-1)} + w(w,v) \\
&= w(P') + w(v,u) = w(P) = d_u^{k}.
\end{align*}
$$
Once again, since the values of $\text{dist}[\cdot]$ never increase, the above inequality must also hold true at the end of the $k$-th iteration of the outer for loop.


Complexity class for polynomial algorithm for 3SAT, but with exponentially large values?

Complexity classes are classes of problems, not classes of algorithms. For example, the existence of Dijkstra's algorithm means that the problem of computing shortest paths in graphs is in P, but it doesn't make sense to say that "Dijkstra's algorithm is in P".

Exponentially large values can be stored in binary in a polynomial numebr of bits, and we can compute on such numbers using a polynomial number of operations. This notwithstanding, it seems that you're trying to get a polnomial-time algorithm that somehow dows exponentially much work, which is an oxymoron.


Are single-dimentional arrays better than multi-dimentional in the GPU?

This is likely going to be dependent on what technology and libraries you use to program the GPU (PyTorch? TensorFlow?  CUDA? BLAS? something else?), and thus seems likely to be out of scope here.  Typically the data must be transferred/copied onto the GPU anyway, so I'd expect the structure of it in RAM only affects the time to transfer to the GPU's memory, not the time to do the GPU computation once it has been copied into GPU memory in the memory layout that the GPU wants.


According to the description you provided the recurrence is correct.
you might think it should be
 T(n)=\begin{Bmatrix}
1 & ,\ n=1\\
T(n-1)\ +\ \Theta(log\ n) & ,\ otherwise
\end{Bmatrix}

because you can find the insertion place by using Binary-Search, however in order to actually insert the element you'll have to move away all the elements in the worst case.