Algorithm to assign producers to consumers with respect to connections I am trying to analyze supply chains in a game and have come across this problem:

First, an informal description: I have producers and consumers. Each producer produces a certain amount of goods, each consumer requieres a certain amount of goods. Each producer is connected to some consumers (these connections have infinite capacity).

Is there a way to transport goods from producers to consumers so that each consumer has sufficiently many goods? Each producer can provide goods to multiple consumers and each consumer can accept goods from multiple producers. A producer also doesn't have to deliver the entire production, as the rest  can be discarted.

The connections form a bipartite graph with producers $p \in P$ and consumers $c \in C$ as vertices (so $V = P \mathbin{\unicode{x228D}} C$) and edges $E \subseteq (P \times C)$. Each producer has a positive production rate and each consumer a positive consumption rate.

We model how much is transported over each connection with a weight function $w: E -> \mathbb{R}$. For each producer $p$ , we get the required production by summing up the weights of all edges incident to $p$. This must not be higher than the production of $p$.

Similarly, for each consumer $c$, we get the total delivery by summing up the weights of all edges incident to $c$. This must not be lower than the consumption of $c$.

Does such a $w$ exist for a given graph, production rate and consumption rate?

The left example has such a function, the right one does not:

I am pretty sure that if we allow negative $w(e)$, the problem is very easy (for connected graphs, just compare total production to total consumption). Therefore, it probably makes sense to restrict $w(e) \geq 0$.

I have tried to find similar problems, but most flow problems have limited flow rates and sources with infinite capacity (whereas here, it's exactly the other way around). I also know about the Assignment problem, but I don't think it applies here.

Perhaps there is a way to slowly remove consumers and producers. In the first example, we know that the top producer can only supply the top consumer, so we could just remove the producer and reduce the consumption rate on the right. It might also be possible to merge multiple producers and consumers if they all supply each other. However, I don't think that these operations alone suffice to solve the problem in all instances.

Perhaps there is no efficient algorithm, so I've also tried proving that the problem is NP-complete, but my attempt to reduce SAT to this problem wasn't successful.

This probably isn't the most enjoyable way to play Anno, but at this point, it don't want to give up...

I'm not sure I understand the problem statement, but it looks like this can be modelled as a network flow problem.  Here's how.  First, create a new source vertex $s_0$.  Then, for each producer $p$, if its capacity is $c_p$,  and add an edge $s_0 \to p$ with capacity $c_p$.  Do that for every producer, then look for a max flow in the resulting flow graph.


Do approximation results for CSPs hold even when domains are of finite but different size? We need to have a precise definition for what a constraint satisfaction problem (CSP) is to study it formally. Looking at a survey by Libor Barto, titled "The Constraint Satisfaction Problem and Universal Algebra", a definition is given in Definition 2.1. Further, it is claimed this is a "standard formal definition of an instance of the CSP over a finite domain".

In particular, the definition says a CSP problem is a triple $(V,D,\mathcal{C})$, where $D$ is a finite domain. In other words, every variable takes a value from the same domain. Tracing back some earlier references from the survey, many papers define $D$ in the same way (i.e., it's the same for each variable).

I'm interested in a definition where each variable $x_i$ has a finite domain $D_i$ of size at most $k$, for some constant $k$. Surely when CSPs are defined like this, it's still NP-complete to decide whether there's a satisfying assingment, and NP-hard to maximize the number of constraints satisfied.

But: can one safely assume approximation results still hold for this definition? More generally, are there approxation results (or other algorithmic results) that break down when domains are of size at most $k$ instead of exactly the same for each variable? It feels strange the "standard formal definition" is not allowing this, so it makes me wonder if there's a reason for this limitation of generality.

This is known as multi-sorted CSPs (a sort in logic is a type of variable). See An Algebraic Approach to
Multi-sorted Constraints by Bulatov and Jeavons, for example.


Time Complexity OF NTM vs TM In Sipser, It is given Pg. 284

Let t(n) be a function, where t(n) ≥ n. Then every t(n) time
non-deterministic single-tape Turing machine has an equivalent 2 O(t(n))
time deterministic single tape Turing machine

In the given proof, at end they conclude

O(t(n)bt(n)) = 2O(t(n)).
where b is the maximum number of legal choices given by N’stransition function

I am unable to understand how did they conclude so>

You can write, if $b\gt 1$,
$$b^{t(n)}=2^{\log_2{b}\times t(n)}=2^{O(t(n))}$$

So,
$$O(t(n)b^{t(n)})=O(t(n)2^{O(t(n))})=O(2^{\log_2{t(n)}}2^{O(t(n))})=2^{O(t(n))}$$

To elaborate,
$$O(x2^{O(x)})=O(2^{\log x}2^{O(x)})=O(2^{O(x)+\log x})=O(2^{O(x)})$$ which means it is eventually upper bounded by some $$c2^{O(x)}=2^{\log cO(x)}=2^{O(x)}$$

Note that if $b=1$, then the non deterministic Turing machine is effectively a deterministic Turing machine, so you can still write it as $O(t(n))$, which is as expected.


How can Subset Sum be in CoNP? On Wikipedia it is Written: NP and co-NP are also thought to be unequal.[1] If so, then no NP-complete problem can be in co-NP and no co-NP-complete problem can be in NP.[2]

So Subset Sum is NP-complete (given integers find a Subset that sums to 0).

CoNp is, the set of decision problems for which a "no" answer has a deterministic polynomial-time verifier.

What does No mean here in the subset sum Example? I can trivally Test if there is a subset that Doesnt sum to Zero.

A $\mathrm{No}$ answer means that there is no solution, not that there is a non-solution.

So for Subset-Sum this means there is no subset of the input integers that sum to zero, or to put it another way, every possible (non-trivial) subset has a non-zero sum. Not that there is a subset which doesn't sum to zero.


How does Hassin's algorithm for the Restricted Shortest Path work? I'm studying the Approximation For Restricted Shortest Path Problem paper and don't understand what he is doing. In particular, I wonder why it is important that one computes upper and lower bounds $UB$ and $LB$ on $OPT$, so that their ratio is below some constant.

The problem is to find the least-cost path from nodes $1$ to $n$ where the cumulative delay (each edge has a delay/transit time in addition to cost) is no more than some $T$.

For the restricted shortest path problem, the exact solution can be found in pseudopolynomial time $\mathcal{O}(|E|OPT)$like this.

  Let $g_j(c)$ be the time of the quickest path form node $1$ to node $j$ with cumulative cost $\le c$.
  \begin{align*}
   g_1(c) & =  0,                                                                                & c = 0,\ldots,OPT, \\
   g_j(0) & =  \infty,                                                                                & j = 2,\ldots,n, \\
   g_j(c) & =  \min\left\{g_j(c-1), \min_{k \mid c_{kj} \le
   c}\left\{g_k(c-c_{kj}) + t_{kj}\right\}\right\}, & j = 2,\ldots,n; ~ c= 1,\ldots,OPT
\end{align*}

So Hassin constructs a $TEST(k)$ procedure which says $YES$ if $OPT \ge k$ and $NO$ if $OPT < k(1 + \epsilon)$

He then proceeds to pick initial bounds $UB$ and $LB$ and uses the $TEST$ to refine them until $\frac{UB}{LB} = 2$. He then computes the final solution with the exact algorithm, but where each edge cost $c_{ij
}$ is scaled as $\hat{c}_{ij} = \lfloor\frac{c_{ij} (n-1)}{LB\epsilon}\rfloor$. So what I would like to know is how this application of the exact algorithm is actually polynomial. I suppose that the optimal solution in this modified graph is somehow bounded, but I do not see where the ratio of $2$ comes into play.

I have one theory now, which is that the final application of the exact algorithm on the scaled costs has complexity $\mathcal{O}\left(|E| OPT\frac{(n-1)}{LB\epsilon}\right) \subseteq \mathcal{O}(|E| 2LB\frac{(n-1)}{LB\epsilon})=\mathcal{O}(|E| 2\frac{(n-1)}{\epsilon})=\mathcal{O}\left(|E|\frac{n-1}{\epsilon}\right)$ which is then polynomial in $n \le \sqrt{|E|}$ and $\epsilon$. Can anybody confirm this?


Proving that the set of grammars generating L or L complement is undecidable Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that both sets are decidable and concluding that UNIVERSALITY is decidable.

UNIVERSALITY problem is $ \{ G \in CFG \mid L(G) = \Sigma^* \} $,
which is known to be undecidable.

I think that the goal is to arrive to the conclusion that UNIVERSALITY is decidable, maybe with a reduction, which means that there is a contradiction in terms of decidabilty of UNIVERSALITY.

Suppose that given a context-free grammar $G$, you could decide whether $L(G) = X$ and whether $L(G) = \overline{X}$. You can use it to decide UNIVERSALITY as follows:

Create a grammar $G_1$ such that $L(G_1) = L(G) \cap X$.
Create a grammar $G_2$ such that $L(G_2) = L(G) \cap \overline{X}$.
Accept if $L(G_1) = X$ and $L(G_2) = \overline{X}$.

The point is that we can construct the grammars $G_1,G_2$ algorithmically.

Note that for some $X$, deciding whether $L(G) = X$ could be decidable. The simplest example is when $X = \emptyset$. A more sophisticated example is $X = w^*$ (this follows from Parikh's theorem, for example).


Kosaraju with connections between SSCs (strongly connected components) First of all I did find similar questions here on Computer Science but nothing what would provide real answer for this problem.

I have a graph which i condense into SSC (strongly connected components) by Kosaraju's algorithm. Now what I need is to find connections between those SSCs. The best would be to somehow inject this process into Kosaraju's runtime but I did not come up with tangible solution there. My algorithm is logically similar to the one on wikipedia: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm (I can't provide my code because it is a school assignment)

I would very much appreciate any tip from smarter folk than me. :D

More information/What I came up with:
I thought about it and did not come up with better solution then after finishing Kosaraju I will go through each vertex, check his in/out edges and if the edge's other side is not part of this SSC than add this edge as connecting edge to my SSC. But this process is very expensive as i need to:

For each vertex go over its all edges
Compare every edge end with vertexes in SSC.

Computation would be something like edges X [vertexes in its SSC]. If my graph would be one huge SSC than I would basically get V*E. There is no way this is best approach, I bet it is actually one of the worst.

Your complexity calculation is incorrect. If for each vertex you go over all of its out edges, in a directed graph you'd only get a $O(|V|+|E|)$ complexity and not $O(|V|*|E|)$. A complexity of $O(|V|*|E|)$ would be the case if for each vertex you performed an operation on all of the edges in the graph, which you have no reason to do.

$O(|V|+|E|)$ complexity is actually the same complexity as calculating the SCCs in the first place, and therefore your general idea can, in-fact, be used (be careful with the details).


Is quadratic nonresiduosity in $\textbf{NP}$? The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an interactive proof system.

Example 1: Let $Z_m^*$ denote the set of integers
between $1$ and $m$ that are relatively prime with $m$.
An element $a \in Z_m^*$ is a quadratic residue mod $n$ [sic] if
$ a = x^2 \mod{m}$ for some $x \in Z_m^*$, else it is a quadratic
nonresidue. Now let $L = \{(m, x) | x \in \mathbb{Z}_m^* \text{is a quadratic nonresidue\}}$. Notice that $L \in \textbf{NP}$: a prover needs only to compute the factorization of $m$ and send it to the verifier without any further interaction.

Given that $n$ is not defined in the context of the example, I assume this to be a typo and that the authors meant $m$. My question is about the last sentence. The authors provide no further detail afterwards about what the verifier would do with this factorization to verify quadratic nonresiduosity. In pursuit of more details, I cracked open Arora-Barak where the following treatment of the above is given in section 8.1 example 8.9.

Here is another example for an interactive proof for a language not known to be in
$\textbf{NP}$. We say that a number $a$ is a quadratic residue mod $p$ if there is another number $b$
such that $a \cong b^2 \mod{p}$. Such a $b$ is called the square root of $a \mod{p}$. ...
the language QNR of pairs $(a, p)$ such that $p$ is a prime and $a$ is
not a quadratic residue modulo $p$ has no natural short membership proof and is not
known to be in $\textbf{NP}$. But it does have a simple interactive proof if the verifier is
probabilistic.

Now if the language QNR described in Arora-Barak is not in $\textbf{NP}$, how could its "superset" the language $L$ described in the paper be in $\textbf{NP}$? If the paper is correct then we could easily construct a verifier which would prove that QNR is in $\textbf{NP}$: for any $(a, p)$ the certificate would consist of the certificate of the membership of $(p, a)$ in $L$ in addition to a certificate for the primality of $p$.

When the modulus is a prime $p$, you can compute quadratic residuosity in polynomial time using the Legendre symbol: $x$ is a quadratic residue mod $p$ iff $(x|p)=1$ or $0$.
When the modulus is a prime power $p^\alpha$, then you can do the same: I believe $x$ is a quadratic residue mod $p^\alpha$ iff $(x|p)=1$ or $0$.  I believe this can be proven using Hensel lifting.
When the modulus is a number $n$ with known prime factorization $n=p_1^{\alpha_1} \cdots p_k^{\alpha_k}$, you can use the Chinese remainder theorem: $x$ is a quadratic residue mod $n$ iff it is a quadratic residue mod $p_i$ for all prime factors $p_i$ of $n$.
This means that quadratic nonresiduosity mod $n$ can be computed in polynomial time when the factorization of $n$ is known or given.  This also means that, as far as I can see, the language QNR should be in NP: a natural certificate is a prime $p$ that divides $n$, and such that $(a|p)=-1$.  The verifier can verify that $p$ is prime in polynomial time and compute the Legendre symbol $(a|p)$ in polynomial time.  At least, that's how it seems to me.
I don't know why Arora-Barak say that QNR is not known to be NP.  This makes me suspect that I may have misunderstood something, as they know way more about computational complexity than I do.


A DFA recognizing my name How can I know if my DFA is implemented correctly?
For example, I need to build a DFA, and then minimize it which will recognize my name.
Language which describe my name is:
L = {pustai, marius}

I came with this solution:

>(0)--p-->(1)--u-->(2)--s-->(3)--t-->(4)--a-->(5)--i-->(6)(goto state 0)
  |
 (7)--m-->(8)--a-->(9)--r-->(10)--i-->(11)--u-->(12)--s-->((13)) (final state)

How can I know if this is implemented correctly?
And about minimization of this automate I think is impossible.

Write down all accepting paths, that is paths from the starting state to final states. These are all the words the given automaton can accept; if the set is the desired one, q.e.d.

This is only possible and a rigorous proof for (co-)finite languages. Once you have cycles you have to apply induction. See here for an in-depth explanation on how to do this for grammars; it's similar for automata.


RSA cryptosystem: Encrypting a signed message I've started to read the section about the RSA cryptosystem in CLRS (page 958) and I don't understand the way it describes how to encrypt a signed message.

If Bob wants to send a message $M$ to Alice:

Bob takes $M$ and encrypts it (using Alice's public key): $P_A(M) = C$.
Sends $C$ to Alice.
She decrypts it using her private key: $S_A(C) = S_A(P_A(M)) = M$.

If Alice wants to send a signed message $M'$ to Bob (page 961):

She computes the digital signature of $M'$ (with her private key): $\sigma = S_A(M')$.
Sends the pair $(M', \sigma)$ to Bob.
Bob receives the pair and check the message authenticity by comparing $M'$ and $P_A(\sigma)$.

If Alice want to send an encrypted, signed message $M'$ to Bob.

In cursive is what I think (I don't know how) it goes.

Alice first appends her digital signature to the message. I guess we get $M'' = M'\sigma$, where $\sigma = S_A(M')$.
Encrypts the resulting message/signature pair with the public key of Bob (the recipient):
Is that $P_B((M'', \sigma))$? What does this mean: $(P_B(M''), P_B(\sigma))$ or $(P_B(M''), \sigma)$?. If the former, then what is the point of encrypting the digital signature?.
The recipient decrypts the received message with his or her secret key to obtain both the original message and its digital signature. I don't how this is done, since I don't know how steps 2 is performed.

Thanks!

Encrypts the resulting message/signature pair with the public key of Bob (the recipient):
  Is that $P_B((M'', \sigma))$? What does this mean: $(P_B(M''), P_B(\sigma))$ or $(P_B(M''), \sigma)$?

Neither. It's simply $P_B(M'')$. The resulting message/signature pair refers to $M''$.


Show that the following language is undecidable $\{ M \mid M
\text{ is a machine that runs in }100n^3 + 300\text{ time }\}$

I am currently stuck with this one. I thought of reducing HALT to M as the reduction seems legitimate to me: if the first is undecidable then building an instance of the first problem starting from the second, ie asking if a machine M that executes an input n stops after a time $f$$(n)$ is like asking if it stops at all and then M ⊆ HALT. However there is something that does not convince me in this demonstration because it seems quite naive and I don't think that this is enough to prove that this language is undecidable. In addition the exercise it is taken from a chapter of a text in which the oracles are introduced, is it possible to prove this language undecidable by means of oracles? I would appreciate your help, thanks.

You haven't defined HALT, so let me assume that it consists of all Turing machines that halt on the empty input. If $M$ halts in time $f(n)$, then in particular it halts on the empty input, and so if $M$ belongs to your language then it also belongs to halt. But the converse doesn't hold, and $L \subseteq HALT$ doesn't imply anything about $L$ (for example, $\emptyset \subseteq HALT$, yet $\emptyset$ is decidable).

In other words, your proof doesn't work. It doesn't prove anything.

Your goal is to show that using an oracle to $L$ (your language), you can decide the halting problem; hence if $L$ were decidable, then so would HALT be, contrary to the known fact that HALT isn't decidable.

In fact, we can show that $L$ is coRE-hard. This means that there is a computable reduction that takes a description of a Turing machine $M$ and outputs a description of another Turing machine $M'$ such that:

If $M$ halts on the empty input then $M'$ doesn't run in time $f(n) := 100n^3 + 300$.
If $M$ doesn't halt on the empty input then $M'$ does run in time $f(n)$.

The construction goes as follows. On input of length $n$, $M'$ simulates $M$ on the empty input for $g(n)$ steps, where $g(n)$ is a function to be determined, which tends to infinity. If $M$ halts within $g(n)$ steps, $M'$ goes into an infinite loop, and otherwise $M'$ halts. We choose $g(n)$ so that the simulation runs in time $f(n)$. (Depending on the exact Turing machine model, we might be able to take $g(n) = n$ or so.)

If $M$ doesn't halt then, by construction, $M'$ also halts within $f(n)$ steps. If $M$ does halt, then for large enough $n$, $M'$ will never halt, and in particular won't halt within $f(n)$ steps.

The language $L$ is also coRE: we can enumerate machines not in $L$ by running all machines on all inputs, and outputting the description of a machine once it doesn't stop within $f(n)$ steps on some input of length $n$. This shows that $L$ is coRE-complete.


How to draw an LTS based on the parallel process "|" in CCS Milner's logic? I'm trying to provide a Hennessy-Milner logic formula for CCS expressions that are not (strongly) bisimilar. An example with a sketch:

  For each of the following CCS expressions, decide whether they are strongly bisimilar and if no, find a distinguishing formula in Hennessy-Milner logic.

$b.a.Nil+b.Nil$ and $b(a.Nil+b.Nil)$

I first draw these two to get a better understanding as follows (excuse my awful drawing skills but I couldn't figure out how to put it in LaTeX so I used draw.io):

You can clearly see the Right Hand Side could do $b.b$ but the Left Hand Side can't respond to that. And my distinguishing HML formula is $[b]<b>tt$. On the LHS you get: $[b]\{b.a.Nil+b.Nil\} = \emptyset$
and on the RHS you get:
$[b]\{b(a.Nil+b.Nil), a.Nil+b.Nil\} = b(a.Nil+b.Nil)$.
Therefore this is a valid distinguishing formula.

Hopefully, I made what the exercise is about clear. Now, the following CCS expressions that I have to distinguish are:

$a.Nil|b.Nil$ and $a.b.Nil + b.a.Nil$.

I know how to draw the RHS because the + denotes a choice but I don't have any idea of how the parallelism work in CCS and couldn't understand it after reading. My guess is the following but it doesn't make sense and is probably wrong:

Could someone help me understand how to sketch the LHS so that I can complete this exercise?

P.S My tags are probably not correct but I couldn't find any tags to Hennessy-Milner logic, so feel free to edit them.

The last LTS in your question is wrong. It should be a diamond-shaped graph, where on one side you perform action $a$ then $b$, and on the other you perform action $b$ then $a$, both sides leading to $\sf Nil$.

This is because the $a$ action is run in parallel w.r.t. the $b$ action, so we get all the possible "interleavings" between such events.

The fixed LTS you posted in the comments looks right, instead.


Pizza commercial claim of 34 million combinations A pizza commercial claims that you can combine their ingredients to 34 million different combinations. I didn't believe it, so I dusted off my rusty combinatorics skills and tried to figure it out.  Here's what I have so far:
From the online ordering site I got the choices

crust (4 types, choose 1)
size  (4 types, choose 1) some crusts are limited to a certain size - not accounting for that, but would like to.
cheese (5 types, choose 1)
sauce  (4 types, choose 1)
sauce level (3 types, choose 1)
meats (9 types, choose up to 9)
non-meats (15 types, choose up to 15)

So I figured this was a combination problem (order is not important) and not an n choose k problem, null is allowed for anything but crust and crust, size, cheese, sauce and sauce level would all be choose only one. Meats and non-meats $2^?$? So that would be:

crust  $\binom{4}{1}=4$
size  $\binom{4}{1}=4$
cheese $\binom{5}{1}=5$
sauce  $\binom{4}{1}=4$
sauce level $\binom{3}{1}=3$
meats $2^9 = 512$
non-meats $2^{15} = 32768$

At this point I'm stuck, how do I combine these to arrive at the total number of possible combinations?

I found this site helpful.

ETA:
If I don't account for the limitations on crust size - some crusts are only available in certain sizes - there are over 16 billion; 16,106,127,360 combinations available, so they were off by quite a bit.

Ok, A bit more detailed answer than in the comments.

Choosing $k$ out of $n$ is done by ${n \choose k} = \frac{n!}{k!(n-k)!}$. So for things like the size of the pizza, where you have 4 options (and you need to choose one, coz pizza cannot be both medium and extra-large at the same times) you have only $4$ options. Indeed, ${4 \choose 1}=\frac{4!}{3!}=4$.

The interesting part are things like the non-meat options. You have 15 and can choose any set of up to 15. Mathematically, this means ${15 \choose 0} + {15 \choose 1} + \cdots + {15\choose 15}$.

As you mentioned, there is a nice formula for such sums:
$$\sum_{i=0}^n {n \choose i} = 2^i$$
thus, for the non-meat options you have $2^{15}=32768$ options, as you said.
(see here for more formulas).

Lastly, to combine all the options, you just multiply them. If you have 4 possible sizes, and, say, 4 possible crusts, then you have $4\times 4=16$ different combinations overall.

So, multiplying everything you get 16.106.127.360, which is larger than 34 million.


sha256 computability class Is it correct to say that since the SHA256 function domain is finite (as reported here) we can build a DFA that calculates this function (i.e. trivially a giant lookup table)?

Furthermore, if we eliminate the limitation on the length of the input, is it correct to say that SHA256 function belongs to the class of $\mathcal{PR}$ primitive recursive functions?

Is it correct to say that since the SHA256 function domain is finite we can build a DFA that calculates this function (i.e. trivially a giant lookup table)?

Theoretically, yes, that's correct. It would require a lookup table of  $2^{2^{64}}$ entries, roughly, encoded as a DFA.

To be more picky, it depends on the notion of "DFA calculating a partial function". In particular, on what we require the DFA to do outside the domain of the function.

If we require non-termination, as we do for TMs, then a DFA can never implement a non-total function since it can not diverge. So, no DFA can compute SHA256.

If we instead only require to reach an "error" state outside the domain (or no requirement at all), then a DFA can compute SHA256.

I'd lean towards the latter interpretation, but here we need indeed to be a little careful with words.

  Furthermore, if we eliminate the limitation on the length of the input, is it correct to say that SHA256 function belongs to the class of $\mathcal{PR}$ primitive recursive functions?

That's correct.

As a general "cannon" result, if an algorithm $A$ has a complexity function which is bounded above by some $\mathcal{PR}$ function $f$, then $A$ implements a function which belongs to $\mathcal{PR}$.

This is because in $\mathcal{PR}$ we can realize the single-step function for TM, mapping a TM configuration to its next one. Then we can recurse on the single-stepping function $f(n)$ times, and read the result in the final configuration.

Corollary: $TIME(O(2^{2^{2^{2^n}}})) \subseteq \mathcal{PR}$.

The unlimited SHA256 surely falls in that obscene time bound.


For signed integers, why don't representative the smallest number as all zeros in binary, and the largest as all ones? I'm reading up on bitwise operators, complements, and two's complements, and I'm wondering why the lower limit of a range (aka lowest negative number) isn't all zeroes in binary, and the upper limit isn't all ones.

For example, for 8 bit integers, why don't we represent -128 as 0000 0000, -127 as 0000 0001, -1 as 0111 1111, 0 as 1000 0000, and +127 as 1111 1111?

This would make it basically impossible to implement the C language. In the C language, a value that can represented both as a signed and unsigned integer must have the same bit representation.

There are other problems, like you can’t use the same hardware for adding signed and unsigned integers, conversion between signed and unsigned requires an actual hardware operation.


Logspace algorithm for s-t connectivity in undirected forests It has been shown that the decision problem
$\{(G, s, t)~\mid~ G\text{ is an undirected forest and there is a path from }s \text{ to } t \}$ is complete for logspace (and therefore in $L$).
But the proof involves a series of reductions which didn't seem very intuitive to me.
Is there any natural algorithm that directly solves this problem in log space?

This is proved by Cook and McKenzie. We make use of the following notation:

$\deg(v)$ is the degree of a vertex $v$.
$N(v,1),\ldots,N(v,\deg(v))$ is some fixed ordering of the neighbors of $v$.

We construct a sequence $v_1,v_2,\ldots$ of nodes starting with $v_1 = s$ and $v_2 = N(s,1)$ (if $\deg(s) = 0$ then $s$ is connected to $t$ iff $s = t$). Given $v_{i-2},v_{i-1}$, we construct $v_i$ as follows:

  Suppose that $v_{i-2} = N(v_{i-1},j)$. Then $v_i = N(v_{i-1},j+1)$.

(If $j = \deg(v_{i-1})$ then $j+1 = 1$.)

It turns out that if the connected component of $s$ has size $m$ then the first $2(m-1)$ vertices contain each vertex $v$ in the connected component exactly $\deg(v)$ times, and after that the sequence repeats indefinitely. This is because the sequence essentially performs a depth-first search, as the following image from Wikipedia illustrates (the arrows should be ignored):

Here $s = F$ and the neighbors are ordered from left to right. The first 16 elements of the sequence are F,B,A,B,D,C,D,E,D,B,F,G,I,H,I,G. The sequence then repeats.

This implies the following simple algorithm: calculate the first $2(n-1)$ members of the sequence, and check whether $t$ ever appears. This can be implemented in logarithmic space.

Reingold gave a (significantly) more complicated algorithm that works for any undirected graph, still using only logarithmic space. If the graph is directed then the problem is complete for NL, and so probably cannot be solved using only logarithmic space (at least not on deterministic Turing machines!).


Minimal, "natural" set of operations to manipulate a binary tree Consider binary trees with some abstract values at the leaves. A tree t2 is said to be "derivable" from a tree t1 iff the set of values in the leaves of t2 is included in the set of values in the leaves of t1. In particular, some values can be removed and some can be duplicated.

I'm looking for a minimal set of somewhat "natural" operations on binary trees that can be composed to transform a tree into any of its derivable trees.

By natural I mean operations which are local to the root of the tree or its vicinity, happen in constant time,  and can be somewhat visualized.

For instance, swapping the left and right subtree of the root of performing AVL like rotations would qualify as natural operations.

It looks like the following set of four operations is sufficient.  They are also minimal / necessary in the sense that no single operation can be removed from the set.

right rotation at the root:

    .            .
   / \          / \
  .  z    =>   x   .
 / \              / \
x   y            y   z

duplicating the tree
deleting the left branch
flipping the right grandchildren

By way of illustration (and a form of proof outline), I've written up a Haskell implementation.  Given a definition of a Tree structure and a TreeOp tree operation type:

data Tree a = Node (Tree a) (Tree a) | Leaf a
type TreeOp a = Tree a -> Maybe (Tree a)

the primitive operations would be defined as:

rotateR, dup, deleteL, flipR :: TreeOp a

rotateR (Node (Node x y) z) = Just $ Node x (Node y z)
rotateR _ = Nothing

dup t = Just $ Node t t

deleteL (Node _ x) = Just x
deleteL _ = Nothing

flipR (Node x (Node y z)) = Just $ Node x (Node z y)
flipR _ = Nothing

We can define derived operations to flip the root's children (duplicate the tree, flip the right grandchildren, and delete the left branch):

flipC :: TreeOp a
flipC = dup >=> flipR >=> deleteL

Similarly, we can define an operation to duplicate the right branch:

dupR :: TreeOp a
dupR = dup >=> rotateR >=> flipR >=> deleteL >=> rotateR

as well as the symmetric variants of all the above operations:

flipL, deleteR, dupL, rotateL :: TreeOp a
flipL = flipC >=> flipR >=> flipC
deleteR = flipC >=> deleteL
dupL = flipC >=> dupR >=> flipC
rotateL = flipR >=> flipC >=> rotateR >=> flipR >=> flipC

Finally, it will be helpful to have an operation for "interleaving" the grandchildren like so:

        ..           ..
       /  \         /  \
      .    .       .    .
     / \  / \     / \  / \
     w x  y z     w y  x z

The best implementation I could come up with was:

interleave =
  -- duplicate the whole tree [[A B] [C D]] [[A B] [C D]]
  dup
  -- select first grandchild:  [[A] [C D]] [[A B] [C D]]
  >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL
  -- select second grandchild: [[A] [C]] [[A B] [C D]]
  >=> flipL >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL >=> flipL
  -- select fourth grandchild: [[A] [C]] [[A B] [D]]
  >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR
  -- select third grandchild:  [[A] [C]] [[B] [D]]
  >=> flipR >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR >=> flipR

With interleave, it's easy to define operations to rotate the left and right subtrees of the root independently:

rotateLR, rotateLL, rotateRL, rotateRR :: TreeOp a
-- rotate left subtree right (i.e., apply `rotateR` to left child)
rotateLR = rotateR >=> flipL >=> interleave >=> rotateL >=> flipL
-- rotate left subtree left (i.e., apply 'rotateL' to left child)
rotateLL = flipL >=> rotateR >=> interleave >=> flipL >=> rotateL
-- rotate right subtree right (i.e., apply `rotateR` to right child)
rotateRR = flipC >=> rotateLR >=> flipC
-- rotate right subtree left (i.e., apply `rotateL` to right child)
rotateRL = flipC >=> rotateLL >=> flipC

Using a helper to apply an operation repeatedly until it no longer works:

untilDone :: (a -> Maybe a) -> a -> a
untilDone op t = maybe t (untilDone op) (op t)

we can turn any tree into an in-order traversal "cons-list-like" normal form:

toList :: Tree a -> Tree a
toList
  = untilDone rotateR
    >>> untilDone (untilDone rotateRL >>> rotateL)
    >>> untilDone rotateR

meaning that, for any tree t whose in-order traversal of leaves is, say, [1,2,3,4,5], the result of toList t will be:

Node (Leaf 1) (Node (Leaf 2) (Node (Leaf 3) (Node (Leaf 4) (Leaf 5))))

Now, this normal form is just a zipper under the rotateL and rotateR operations -- we can rotateR it to any point in the list, with the "rest" of the list elements on the right branch in normal form, and the preceding elements on the left branch in an "inverted" normal form (with leaves on the right branches instead of the left).

Applying interleave to such a zipper will swap adjacent elements at the zipper's cursor in the general case, though the following function also handles the corner cases where interleave fails because the left or right branch is just a leaf:

swapLeaves :: TreeOp a
swapLeaves = interleave
  `orTry` (rotateR >=> flipR >=> rotateL)
  `orTry` (rotateL >=> flipL >=> rotateR)

Here, orTry isn't a separate operation -- it's just a conditional control structure that handles the case where a generalized operation fails because, say, the left branch is only a leaf instead of a larger inverted cons list:

orTry :: TreeOp a -> TreeOp a -> TreeOp a
orTry op1 op2 t = op1 t <|> op2 t
infixl 1 `orTry`

We can also duplicate the element to the left of the cursor with:

dupLeaf :: TreeOp a
dupLeaf = (flipL >=> rotateR >=> dupL >=> rotateL >=> flipL >=> rotateLR)
  `orTry` dupL

This doesn't handle two corner cases: we can duplicate the rightmost element (i.e., duplicate an element to the right of the cursor) with a swapLeaves >=> dupLeaf => swapLeaves => rotateR => swapLeaves combination, and if the tree is a lone leaf, we can just duplicate it with dup.

We can delete the element to the left of the cursor with:

deleteLeaf :: TreeOp a
deleteLeaf = (flipL >=> rotateR >=> deleteL) `orTry` deleteL

and the last element with a swapLeaves >=> deleteLeaf combination`.

I think it's clear that with there operations to swap, duplicate, and delete leaves together with rotations through the zipper, we can turn any in-order cons list into any other in-order cons list constructed from a subset of its elements.

And, since toList uses only reversible operations, it follows that we can reconstruct the final tree from its in-order cons list, so I think that probably completes the proof that these operations are sufficient.

To establish that they're "minimal" / necessary, we need to show that dropping any one of the primitive operations would make it impossible to handle some case.  It's easy to see that dup and deleteL are necessary, as they're the only operations that can add or remove leaves, respectively.  With the exception of rotateL, all the other operations preserve the binary tree property of "perfection" or "perfect balance" (i.e., the property of having all leaves at the same level), so rotateR is necessary to create an unbalanced tree from a perfectly balanced one.  And finally, flipR is necessary as no remaining operations can change the in-order traversal of a tree's leaves (oops -- actually, this isn't convincing, since dup and deleteL can do this; I'll need to think about this one).

Anyway, here's the full code to play with:

{-# OPTIONS_GHC -Wall #-}
import Data.Maybe (fromJust)
import Control.Monad
import Control.Applicative
import Control.Arrow ((>>>))
data Tree a = Node (Tree a) (Tree a) | Leaf a
data Side = L | R
type TreeOp a = Tree a -> Maybe (Tree a)

rotateR, dup, deleteL, flipR, interleave :: TreeOp a

rotateR (Node (Node x y) z) = Just $ Node x (Node y z)
rotateR _ = Nothing

dup t = Just $ Node t t

deleteL (Node _ x) = Just x
deleteL _ = Nothing

flipR (Node x (Node y z)) = Just $ Node x (Node z y)
flipR _ = Nothing

flipC :: TreeOp a
flipC = dup >=> flipR >=> deleteL

dupR :: TreeOp a
dupR = dup >=> rotateR >=> flipR >=> deleteL >=> rotateR

flipL, deleteR, dupL, rotateL :: TreeOp a
flipL = flipC >=> flipR >=> flipC
deleteR = flipC >=> deleteL
dupL = flipC >=> dupR >=> flipC
rotateL = flipR >=> flipC >=> rotateR >=> flipR >=> flipC

interleave =
  -- duplicate the whole tree [[A B] [C D]] [[A B] [C D]]
  dup
  -- select first grandchild:  [[A] [C D]] [[A B] [C D]]
  >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL
  -- select second grandchild: [[A] [C]] [[A B] [C D]]
  >=> flipL >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL >=> flipL
  -- select fourth grandchild: [[A] [C]] [[A B] [D]]
  >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR
  -- select third grandchild:  [[A] [C]] [[B] [D]]
  >=> flipR >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR >=> flipR

rotateLR, rotateLL, rotateRL, rotateRR :: TreeOp a
-- rotate left subtree right (i.e., apply `rotateR` to left child)
rotateLR = rotateR >=> flipL >=> interleave >=> rotateL >=> flipL
-- rotate left subtree left (i.e., apply 'rotateL' to left child)
rotateLL = flipL >=> rotateR >=> interleave >=> flipL >=> rotateL
-- rotate right subtree right (i.e., apply `rotateR` to right child)
rotateRR = flipC >=> rotateLR >=> flipC
-- rotate right subtree left (i.e., apply `rotateL` to right child)
rotateRL = flipC >=> rotateLL >=> flipC

untilDone :: (a -> Maybe a) -> a -> a
untilDone op t = maybe t (untilDone op) (op t)

toList :: Tree a -> Tree a
toList
  = untilDone rotateR
    >>> untilDone (untilDone rotateRR >>> rotateL)
    >>> untilDone rotateR

swapLeaves :: TreeOp a
swapLeaves = interleave
  `orTry` (rotateR >=> flipR >=> rotateL)
  `orTry` (rotateL >=> flipL >=> rotateR)

orTry :: TreeOp a -> TreeOp a -> TreeOp a
orTry op1 op2 t = op1 t <|> op2 t
infixl 1 `orTry`

dupLeaf :: TreeOp a
dupLeaf = (flipL >=> rotateR >=> dupL >=> rotateL >=> flipL >=> rotateLL)
  `orTry` dupL `orTry` dup

deleteLeaf :: TreeOp a
deleteLeaf = (flipL >=> rotateR >=> deleteL) `orTry` deleteL

pprint :: (Show a) => Tree a -> IO ()
pprint = putStrLn . unlines . pshow
pshow :: (Show a) => Tree a -> [String]
pshow t = case t of
  Leaf x -> [center 5 $ show x]
  Node x y -> bar ++ xy'
    where x' = pshow x
          y' = pshow y
          xy' = hjoin x' y'
          lft = width x' `div` 2
          rgt = width y' `div` 2
          rest = width xy' - lft - rgt
          bar = [ justify lft rgt $  '.' : replicate (rest - 2) '-' ++ "."
                , justify lft rgt $  '|' : spaces (rest - 2) ++ "|" ]
  where
    spaces = (`replicate` ' ')
    justify l r str = spaces l ++ str ++ spaces r
    width = length . head
    center n str = justify l (l+u) str
      where (l, u) = (n - length str) `divMod` 2
    hjoin x y = go x y
      where wx = width x
            wy = width y
            go (l:ls) (r:rs) = (l ++ r) : go ls rs
            go [] rs = map (spaces wx ++) rs
            go ls [] = map (++ spaces wy) ls

t1, t2 :: Tree Int
t1 = Node (Node (Leaf 1) (Leaf 2)) (Node (Leaf 3) (Leaf 4))
t2 = Node t1 (Node (Node (Leaf 5) (Leaf 6)) (Node (Leaf 7) (Leaf 8)))

main :: IO ()
main = do
  pprint t1
  pprint . fromJust $ interleave t1
  pprint . fromJust $ toList >>> rotateR >=> rotateR $ t1


Running programs backwards I never used a debugger that can run a program backwards but I would like to. Now I wonder if there is much evidence and theory about backwards runnable programming, when and why a program can be run backwards or when and why not?

Intuitively I find that the computer should be able to run the program backwards, if it once has run the program forward knowing that the program will run backwards hence saving states of the program that otherwise might get lost and deallocated.

Debugging is just a practical example. I'm also interested in it for the sake of the theory of reversibility, if the program can be run backwards, then what the program does is reversible, isn't it?

There's lots of research on this subject.  I've sometimes seen it called "time-travel debugging" in the literature, sometimes "reverse debugging".  A few minutes on Google Scholar should turn up a bunch of research publications on the subject.

See also https://softwareengineering.stackexchange.com/q/181527/34181 and https://stackoverflow.com/q/1470434/781723.


How is CFL-reachability solvable in exponential time and space? I have read a paper which mentions that CFL-reachability is solvable in exponential time and space. Intuitively, I suppose that one need to explore through all the sub-paths in the PDA for a CFL. However, I am not able to convince myself with this explanation. If someone could provide an explanation, it would be great.

Please refer to the paper Program Analysis via Graph Reachability by
Thomas Reps where he mentions clearly that CF-reachability is solvable in cubic time.

I assume CFL-reachability is defined as follows:

A CFL-reachability problem is  where a path is considered to connect two nodes only if the concatenation of the labels on the edges of the path is a word in a particular context-free language (an $L$-path):

Definition 2.1 (from paper above). Let $L$ be a context-free language over alphabet $\Sigma$, and let $G$ be a graph whose edges are
labeled with members of $\Sigma$. Each path in $G$ defines a word over $\Sigma$, namely, the word obtained by concatenating, in order, the labels of the edges on the path. A path in $G$ is an $L$-path if its word is a member of
$L$.


Selection in expected linear time: Why am I getting $O(n)$ bound instead of $\Omega(n \lg n)$? The problem is from CLRS 9.3-1:

  In the algorithm SELECT, the input elements are divided into groups of
  $5$. Argue that SELECT does not run in linear time if groups of $3$ are used.

If we do the "divide by $3$" technique, we will come up with this recurrence --

$$T(n) = \begin{cases}
\Theta(1) & \text{if $n \le K$} \\
T(\lceil n/3 \rceil)+T(2n/3+4) + O(n) & \text{if $n \ge K$}
\end{cases}$$

I have solved by substituting $T(n) \le cn$ and  $O(n) = an$ --

$$\begin{aligned}
T(n) & \le \lceil n/3 \rceil + c(2n/3 + 4) + an \\
     & \le cn/3 + c + 2cn/3 + 4c + an \\
     & = cn + 5c + an \\
     & = (c+a)n + 5c \\
     & = c_1n + c_2 \le c_1n \approx O(n)
\end{aligned}$$

But the solution says it should be $\Omega(n \lg n)$. I understand that substitution like $cn \lg n$ could give $\Omega(n \lg n)$ bound, but what is wrong with $O(n)$ formulation above?

You started with the induction hypothesis $T(k) \le ck/3$ for all $k<n$, but you didn't prove that $T(n)\le cn$.  You concluded that $T(n) \le c_1 n$, for a different constant $c_1 \ne c$.  For the induction proof to work, you have to use the same constant in the induction hypothesis and the conclusion.


Does the normal form theorem imply that every partially computabe function is primitive recursive? This is Normal Form Theorem (Second Edition of Computability, Complexity, and Languages written by Martin Davis page 75):

Let $f(x_1,...,x_n)$ be a partially computable function. Then there is a primitive recursive predicate $R(x_1,...,x_n,y)$ such that:
$f(x_1,...,x_n) = L(min R(x_1,...,x_n,z)_z)$ (minimization is on z)

So I think an immediate result of this theorem is that every partially computable function is primitive recursive and every primitive recursive function is partially computable. is it true?

No it not true. Primitive recursive functions are a subset of computable functions. The minimization operator from $\mu$-calculus is not primitive recursive and not guaranteed to terminate. The constantly false function for instance would cause minimization to loop infinitely. As you likely know primitive recursion is guaranteed to terminate.

What does seem to follow from this is that every computable function is $\mu$-recursive as primitive recursion is a subset of $\mu$-recursion. In fact I happen to know this to be true because $\mu$-recursion is turing complete.

You can check out primitive recursion and $\mu$-recursion on Wikipedia.

I also found a wikipedia page with some related matters. In particular they give another form of the Normal Form Theorem that seems slightly stronger; see here.


Zero-based array implementation with logarithmic insertion time Normal zero-based arrays (ie not those with a sort order) have constant lookup time, but linear insertion time.

For a specific problem I was musing about a balanced tree that would allow for an zero-based array implementation with logarithmic time for all of the following operations: insertion, removal and finding the next and previous element.

I'm reasonably sure it should be straight-forward to implement: The non-leaf nodes would have to store the count of elements in their left branch respectively.

Such a data structure should be useful in text editors, as the user obviously can insert text anywhere in the document and yet the editor is supposed to render a screenfull of text around a given location quickly as well.

My question: What's this data structure called? Is there a buzzword I can google? (Such as "B-tree", "red-black tree", etc. for key-ordered search trees?)

All tree data structures that use pointers can be re-worked to use array indices as well, and that is probably your best bet. If you come across a design that uses NULL pointers, use the array index $-1$ to represent NULL.

In general, the best kind of structure to look for (and to arrayify if that is what you want to do) is a rope, which is a stronger kind of string (see Wikipedia). Ropes are designed for exactly this purpose.


practise resources for basic sorting I have to prepare for a midterm and I am looking for a resource where I can practise the three basic sorting algorithms insertion sort, bubble sort and selection sort a little.

Last year they had to sort an array with n elements and the elements were integers with values between 0 and m-1 and the complexity had to be of O(n+m).

I did not find any good resources as most of them deal with more advanced topics and prepare you for interviews.

So I would be glad if someone could give me a good hint.

What do you mean by "practice sorting"? Sets of data to sort by hand? Just whip something up with a random number generator. Examples showing how the methods work? At least Wikipedia has detailed algorithms with pretty animations, or search for "algorithm animation", it is quite popular.


Runtime of sorting a partially-sorted array I have an array of $n$ items which is partially sorted like below:

$$A[i]\le{A[i+k]}$$

where:

$$i=1,2,...,n-k$$

For sorting the array completely, I wonder what the runtime big O is.

I feel only an array of size $k$ needs to be sorted. Because if the sub-array $A[1\le{i}\le{k}]$ is sorted, then all the subsequent sub-arrays are automatically sorted: $A[1+k\le{i}\le{2k}]$ and $A[1+2k\le{i}\le{3k}]$ up to $A[n-k\le{i}\le{n}]$

Therefore the runtime big O might be just $O(k\log{k})$

Your argument is not correct: Even if the subarrays a[0] to a [k-1], a [k] to a [2k-1] and so on are sorted, that doesn't make the whole array sorted. For example if k = 3 you could have [1, 2, 10000, 3, 4, 10001, 10002, 10003, 10004] and there's still a lot of sorting to be done.

You basically have k sorted sequences of length about n/k, so you have k sequences to merge, which you should be able to do in O (n log k).


Problem related to set partitioning Let $A_j=\{(a^i_j,b^i_j)~:~ 0 \leq i \leq n,\text{and }  a^i_j,b^i_j \in \mathbb{Z}^+\}$

Given sets $A_1,\ldots, A_{p}$ and a positive integer $k$, the problem is to check whether there exists one element $(a^{i_j}_j,b^{i_j}_j)$ from each $A_j$ such that $\sum_{j}^{} a^{i_j}_j \geq k$ and  $\sum_{j}^{} b^{i_j}_j \geq k$.

It looks like the problem is related to set partitioning problem, however, I am not sure how to get a reduction from set partitioning problem.  Can someone help me to find the algorithm to solve this problem?

Let $OPT[t, x]$ be the maximum value of $\sum_{j=1}^t  b_j^{i_j}$  that can be attained by selecting one element $(a_j^{i_j}, a_j^{i_j})$ from each of the first $t$ sets with the constraint that $\sum_{j=1}^i  a_j^{i_j} \ge x$.
If the constraint cannot be satisfied, let $OPT[t, x] = -\infty$.

According to the above definition we have $OPT[0, 0] = 0$ and $OPT[0, x] = -\infty$ for $x > 0$.

For $t>0$ we have:
$$
OPT[t,x] = \max_{i=1, \dots, n} \left( b_t^i + OPT[t-1, \max\{x-a_t^i, 0\}] \right).
$$

The answer to your problem is "yes" if and only if $OPT[p, k] \ge k$.

Since there are $O(p \cdot k)$ subproblems, each of which can be solved in $O(n)$ time, the overall time complexity of this algorithm is $O(p \cdot k \cdot n)$.

To show that your problem is NP-hard, you can notice that it is a generalization of partition problem: given a set $S = \{x_1, \dots, x_m\}$ of $m$ non-negative integers, decide whether there is a subset $S'$ of $S$ such that $\sum_{x \in S'} x = \frac{1}{2} \sum_{x \in S} x$.

To see this, define $n=2$, $p=m$, $A_j = \{ (x_j, 0), (0, x_j) \}$, and $k = \frac{1}{2} \sum_{x \in S} x$.


Implementation of caches on CPUs with pipelines I've read that some current CPUs (e.g. Intel i7 and ARM A9) have (L1) cache latencies of multiple clock cycles while also being pipelined. Some devote multiple pipeline stages to instruction fetching.

How is the L1 cache implemented to support pipelining?

Is it, say, $k$ actual stages for decoding the address or does it use some asynchronous multiport logic with a datapath latency set to $k$ clock cycles?

http://caps.cs.binghamton.edu/papers/aggarwal_ics_2005.pdf

I've found this paper which explains in the introduction that with higher associative caches the datapath to read data, compare tags and drive output becomes too long to use with high clock frequencies. Therefore the cache access is split into the 3 stages: decode set, compare tags and read, drive data. It goes further and explains that the access can have an extra stage added to avoid redundent reads of data and only read data after comparing and matching the correct tag, which improves power usage.

Although not really related to my question the paper also explains cache set and way prediction techniques to reduce the latency by parallelising address calculation and the cache read operation, the original paper refers to an article on the alpha 21264 microprocessor on how to implement the prediction.
http://mixteco.utm.mx/~merg/AC/pdfs/alpha_21264.pdf

The technique is to reduce the latency by not waiting on the address calculation stages in the CPU pipeline. This is done by predicting the address of the data to be read and checking at the end of the operation.


what is the need for valid/invalid bit in paged memory technique? How is the valid/invalid bit in paged memory useful?
I am not able to understand the significance.
Is it also somehow used to share the processes among different users.

In a typical multilevel page table implementation on a typical modern operating system, any attempt to access memory for a page whose page table entry set to "invalid" (typically 0) causes a page fault. This is a hardware trap which transfers control to the operating system.

The most obvious use for this is to represent a region of address space for which there is genuinely nothing there. When a user-space application starts, it will have some of its virtual address space allocated (e.g. for program text, data, BSS, stack, etc). Additional memory (e.g. memory for heap storage or memory-mapped files) needs to be requested from the operating system. This means that a lot of the address space of the process is "blank", and any attempt to access those addresses should fail. The page table entries for these addresses are therefore marked as invalid.

(As an aside, most modern operating systems also use this to support the NULL pointer in C. The first few pages of the address space of a process are deliberately left invalid so that any attempt to access memory through a NULL pointer is trapped by the operating system. Even the first 1MB is not unknown.)

An alternative way to think of the validity bit is that if a program tries to access an invalid page, this causes a trap to the operating system. So the question you might want to ask is: Why would an operating system want that?

One use is to represent a page which is valid (in the sense that it is correct for the user program to access that address) but not currently backed by a physical page. For example:

Demand-paged memory, where the address represents part of a memory-mapped file (that might include the program that is running), or a page that has been swapped to secondary storage. In this case, attempting to access the memory causes the operating system to read in the data before the program continues.
Most modern operating systems support zero-fill memory. When an application allocates memory, the typical default is that this is not backed by physical memory until it is first used. The way this is supported by using the invalid bit.
A related idea is copy-on-write memory, which is used (for example) to implement fork() in Unix.

And there are a bunch of related operating system housekeeping-like tasks for which manipulating the valid bit is useful. For example:

Paging out memory requires detecting what pages have been recently used so that infrequently used pages can be paged out. One way to do this is to mark the page as invalid for a short time. If the page is used in that time, operating system knows that it was accessed because a page fault occurred. (Modern Intel CPUs have a more efficient mechanism for this, but the valid bit works if you're using a CPU where that isn't supported.)
An operating system will often mark a dirty page (e.g. a modified page which represents a memory-mapped file) as invalid while it is being flushed to secondary storage. Any program which tries to modify a page which is in the process of being flushed should wait until the write is complete, so that the data being written is in a known state.
Operating systems can use the validity bit to help debuggers. Many modern debuggers let you set a breakpoint which fires if a certain variable is read or modified. One way to implement this is through the page fault mechanism.

Basically, any time that it would be useful to handle a memory operation by trapping to the operating system is a time when it would be useful to mark a page as invalid.


Count in relational algebra using Ω = { π, σ, ⋈, ⋉, β, x, ∪, ∩ , - } schema(author)={name, newspaper}

The table contains a list of authors. Each author works for a newspaper. So a single newspaper may employ multiple authors. How can I get the names of the newspapers that have at least two authors working for them? My algebra consists of:

Ω = { π, σ, ⋈, ⋉, β, x, ∪, ∩ , - }

There is no count in the algebra. So I am limited to the above Ω. Any ideas how I can implement counting?

Hint: to express "the set $S$ has size $\ge 1$" in propositional logic (without using the "size" operator), you can write $\exists x . x \in S$.  How would you express "the set $S$ has size $\ge 2$"?  Does that give you any ideas for how to use relational algebra to solve your question?


Short notation for Turing machine configurations I'm writing about Turing machines and often need to denote the tape. I'm using exponential tapes, i.e. a repetition count for each symbol.

I usually use something similar to
$(x_k^{e_k})_{1 \leq k \leq m} \text{ Q } (x_k^{e_k})_{m+1 \leq k \leq n}$
(latex: $(x_k^{e_k})_{1 \leq k \leq m} \text{ Q } (x_k^{e_k})_{m+1 \leq k \leq n}$)
with $x_k$ the symbols and $e_k$ their exponents. The head in state $Q$ is at position $m$.

What (very slightly) annoys me about this is the need to include $Q$. Without it, it would just be
$(x_k^{e_k})_{1 \leq k \leq n}$
(latex: $(x_k^{e_k})_{1 \leq k \leq n}$)
, which is must easier to read.

The transitions may change various symbols and exponents at the same time, while $Q$ almost always stays in the same spot.

How should I note this down? Is there an easy to understand (and parse) notation which is shorter but still carries the same information? I could not find a solution in the papers I read. Or maybe I should just carry on, because this isn't an issue at all?

This is just a convention. You can write a configuration as the tuple that has the same information. Eg, a possible way to write a configuration is as the tuple
$$Config= (tape,state,pos)$$

where $tape$ is the non empty tape content, $state$ is the current state, and $pos$ is the position of the head.

This is fully equivalent to the method you use, which makes sense for other succinct description of configurations. Tho only thing to bear in mind, is that people are used to the 1-string-head-inside convention you describe in the question, so if you change it, you need to be very clear and explicit about it.


Hamming distance required for error detection and correction I have already asked a pair of questions on the hamming distance, hamming code, valid and invalid codewords on this website, because I cannot understand those concepts fully, and in a few weeks or less, I am going to have an exam also on those topics, I really do not understand. I have tried to take a look to wikipedia articles, but it is, for me, quite complicated to understand.

My question this time is more concrete. I have a figure, representing how many errors can we detect and correct according to the hamming distance. The thing I am not understanding is why, for example, with an hamming distance of 3, we can just detect 2 bit flips and correct 1 bit flip. I know there are 2 formulas (that you can see in the picture), which bring us to that result, but I would like understand why those formulas are correct. Why, with an hamming distance of 3, we can just detect 2 errors and correct 1.

This is picture:

The Hamming distance being 3 means that any two code words must differ in at least three bits. Suppose that 10111 and 10000 are codewords and you receive 10110. If you assume that only one bit has been corrupted, you conclude that the word you received must have been a corruption of 10111: hence, you can correct a one-bit error. However, if you assume that one or two bits could have been corrupted, you don't know if 10110 should be 10111 (one 1 got turned into a 0) or 10000 (two 0s got turned into 1s). You can correct one-bit errors (if you assume that those are the only kind that occur) but you can't tell the difference between a one-bit error from one codeword and a two-bit error from another, so you can't deal with two-bit errors at all. If a two-bit error occurs, you'll detect that some error occurred, but you'll assume it was a one-bit error from a different codeword and "correct" it wrongly.

In contrast, with the distance-4 code illustrated in the fourth diagram, you can detect two-bit errors.  If you receive the word in the middle, you can tell that (at least) two bits got corrupted but you can't tell whether you were supposed to see the blue codeword on the left or the one on the right.


High maths for game theory I am a starting Ph.D. student in computer science, and I am trying to understand some classic game-theory papers, such as those by Nash, Kalai and Smorodinsky.   But I find it hard to understand the mathematical parts. It seems that these papers were written by mathematicians, for mathematicians.

Can you recommend a book that explains the mathematical preliminaries of game theory, to people without extensive mathematical background?

[The reviews are based on my first hand experience with the materials.]

Quick Read:

Essentials of game theory
(Leyton-Brown, Shoham) - This is a ~100 page book, which will give a strong intuition (and more) on Game theory, this mostly covers the basics, the math here is also pretty lightweight, and this is very much readable (even by a college junior). After this book the reader should be able to (atleast) sit through an advance GT Talk.
An Algorithmic Game Theory
Primer (Tim
Roughgarden) - A really nice survey by Tim Roughgarden. It talks about various disciplines like Mechanism Design, Complexity of Equilibria, among many other things.This should motivate the reader to identify the other areas of research.

Books:

Algorithmic Game Theory (Nisan et al) - This is perhaps the most popular book among Computational Game Theorists.. It covers a lot of ground, and the content is very rich. (IMHO) This is one of the books, that every researcher should read before diving into the subject.
Lectures in Game Theory for Computer Scientists (eds. Apt and Grädel) This is yet another book that contains essays from several authors and is rich in application content. As the name suggests, this is for a great resource for computer scientists who want to use game theory for their research.

Also, if you are done with these, want more advanced material take a look at the LNCS Proceedings of SAGT.


Regularity condition in the master Theorem in the presence of Landau notation for f There already are many questions and answers about the importance of the regularity condition in case 3 of the Master Theorem. My question is about when can we safely assume the regularity condition is satisfied when f is only provided as a $\Theta(g(n))$, which is actually what happens most of the time when we don't want to bother detailing the exact expression for $f$.

From my understanding, I believe that nothing can be assumed without additional information on f. In the example provided on wikipedia of $T(n) = T\left(\frac{n}{2}\right) + n(2 - \cos{n})$ we have $f(n) = \Theta(n)$ since $(2 - \cos{n}) \in [1, 3]$. Yet $f$ does not satisfy the regularity condition and we therefore cannot deduce that that $T(n) = \Theta(n)$.

Going down the definition of $f(n) = \Theta(g(n))$, we have $n_0 \geq 0$, $c_0 > 0$ and $c_1 > 0$ such that for every $n \geq n_0$ $c_0 g(n) \leq f(n) \leq c_1 g(n)$. Let's assume $g(n) = n^c$.

Given a Master Theorem instance of $T(n) = aT\left(\frac{n}{b}\right) + \Theta(n^c)$, we are in case 3 of the Master Theorem when we have $a < b^c$. Now to check the regularity condition we need to check that $a f\left(\frac{n}{b}\right) \leq kf(n)$ for some $k < 1$. We therefore have that for $n \geq n_0$
$$
  \begin{aligned}
    af\left(\frac{n}{b}\right)
      &\leq a c_1 g\left(\frac{n}{b}\right)\\
      &\leq a c_1 \frac{n^c}{b^c}
  \end{aligned}
$$
and
$$
  \begin{aligned}
    kf(n)
      &\geq k c_0 g(n)\\
      &\geq k c_0 n^c
  \end{aligned}
$$
assuming $n > 0$, we therefore need that
$$
  \begin{aligned}
    k c_0 &\geq \frac{a c_1}{b^c}\\
    k &\geq \frac{c_1}{c_0}\frac{a}{b^c}\\
  \end{aligned}
$$

In the Wikipedia example, we have $\frac{c_1}{c_0} = 3$ and $\frac{a}{b^c} = \frac{1}{2}$. We would therefore need that $k \geq \frac{3}{2}$ which contradicts $k < 1$.

Now when $f$ just comes out of a loop intrication without inner tests that would make the worst and best cases different, $f$ is a polynomial, and we just use its dominant power as a $\Theta$. I believe what saves us is that we can choose the $n_0$ in the Landau notation, and by increasing it we can have $\frac{c_1}{c_0} < \epsilon$ for any $\epsilon > 1$. And since $\frac{a}{b^c} < 1$, we can always find some $n_0$ such that for any $n \geq n_0$, the regularity condition is satisfied.

Is this sound ? Can we use the generalized Akra-Bazzi Theorem to just not bother ?

Suppose that $T(n) = aT(n/b) + \Theta(f(n))$. What this means is that $T(n) = aT(n/b) + g(n)$, where $g(n) = \Theta(f(n))$, say $c_{LB} f(n) \leq g(n) \leq c_{UB} f(n)$. Consider now the following two recurrences:
$$
T_{LB}(n) = aT_{LB}(n/b) + c_{LB} f(n), \\
T_{UB}(n) = aT_{UB}(n/b) + c_{UB} f(n),
$$
with the same initial conditions as the initial recurrence. You can show inductively that $T_{LB}(n) \leq T(n) \leq T_{UB}(n)$. Assuming that the function $f(n)$ does satisfy the regularity conditions, you can use the master theorem to solve the two auxiliary recurrences, and hence to deduce the solution to the original recurrence.


Support Vector Machines as Neural Nets? This is more of a conceptual question.

I have learned about Neural Nets, and I have some clue as to how Support Vector Machines work. I read somewhere however that given the appropriate kernel (is that right?), the SVM is identical to the Neural Net. Could someone who understands this please enlighten me as to how that's possible?

An SVM with a linear kernel has the same expressive power as a single perceptron in a neural net, since both are linear classifiers. If you think of the kernel function as mapping your input to a higher dimensional feature space then the SVM is still a linear decision boundary in that high dimensional kernel space. You could theoretically use the high dimensional kernel space features as input to a neural network as well as long as the kernel space is finite. Again the linear SVM behaves similarly to a single perceptron.

However, this only applies to linear SVMs.  In practice SVMs are typically used with a non-linear kernel, and then no such equivalence applies.  So this claimed equivalence might be a bit misleading, if you are comparing how SVMs tend to be used in practice to how neural nets tend to be used in practice.

Summary: Think of an linear SVM as being similar to a single perceptron instead of a neural network.


What is the term for this set I have a set of related data/objects for which, when undergoing some algorithm, there should be only one valid match. Is there a unique term for this type of set?

A common practical use case would be a list displayed for user selection, or a list of keys that should have a single corresponding entry in a database table.

To illustrate this, here are a few examples:

[True, False]  (boolean)
[Forward, Neutral, Reverse] (state machine status)
[Rare, Medium, Well] (user preference)
[Credit, Debit] (reference type)

In each of these cases, only one element in the set will be contextually valid, where the context may be a database record, an instance of an object in memory, or a question on a survey.

Examples of sets that wouldn't meet this criteria:

[Garage, Kitchen, Bedroom, Bathroom] (rooms in a home)
[Email, Phone, Text] (method of communication)
[All Countries in Europe] (places I visited)

In these cases, the set is used as a bucket from which a selection may be made - but the selection is not necessarily expected to be a single item in the set.

None of your examples holds up: each has queries that allow multiple answers, and each has queries that allow only singleton answers.

So you are really after a property of queries.
On the most abstract level, given a set $S$ the term you are looking for is function:

$\qquad f : Q \to S \\
\qquad f(q) = s \text{ s.t. } q(s) = 1$

where $Q$ is the set of queries (predicates), i.e. $Q \subseteq S \to \{0,1\}$. Note how $f$ is a (well-defined) function if and only if all $q \in Q$ have a support (set of values on which $q$ is $1$) of size $1$.

If queries end up being true for (i.e. returning) multiple values, we call $f$ a relation. Or, alternatively, a function that maps queries to (possibly empty) sequences of results, i.e.

$\qquad f : Q \to S^*$.


A data structure that makes finding close objects easy I’m working on a project that involves a robot and a very large number of reference points. The robot moves around, while the reference points are fixed in space. I would like the robot to be able to tell which reference points are within a fixed distance of it at any point in time. This must be done in an online fashion. There are a very large number of reference points, so iterating through the list is impractical.

This is in many ways similar to a priority queue, but I don’t see any way to adopt that data structure to this context. Every move would require recalculating the distances which appears to require iterating over the entire list of reference points after every move.

Is there a data structure that works for this context? I can allow for a large amount of precomputation if necessary, though the robot’s path isn’t known in advance so I can’t precompute all the relevant distances or something like that. Iterating over the list of reference points can be done during precomputation, just not online because [number of points] * [number of moves] is too large. A solution that is linear in points and sublinear in moves may be feasible, but I would be highly surprised to learn it exists.

I would also be interested in a data structure that tracks the closest waypoint, if that is feasible but the general question is not.

Data structures designed to organize multi-dimensional data can help, for instance quad trees or, more generally, k-d-trees.

It might also be possible to apply ideas from sweep-line algorithms, sweeping outwards radially from the current position of the robot.


Does NP mean verifiable in polynomial time or solvable in polynomial time? Is NP defined as verifiable in polynomial time, or solvable in polynomial time? Verifiable meaning that the solution can be checked in polynomial time, and solvable meaning that the solution can be found in polynomial time?

NP is a class of problems whose solution is verifiable in polynomial time on a deterministic Turing machine.
Alternatively, NP is a class of problems whose solution is solvable in polynomial time on a nondeterministic Turing machine.

Please look here.


Finding k-nearest neighbors to a set of nodes in a large graph Given a large graph $G=(V,E)$, a set of nodes $S\subseteq V$, the problem is finding the $k$-nearest nodes in $V$ to the nodes in $S$.

Given a pair of nodes $(u,v)$, the distance $d(u,v)$ between $u$ and $v$ is defined as the length of the shortest path between them. Hence, the lower the distance is, the closer two nodes are.

The 1st nearest neighbor $n\in V$ to the set $S$ has the minimum sum of the distance to all the nodes in $S$.

Finding $n \in V$ to minimize $\Sigma_{s \in S}$  $d(s, n)$

I think solving a unique facility location problem with $S$ as the client nodes can be an answer for the problem when k=1. However, it may not provide a correct answer when k>1 since to the best of my knowledge, if the facilities are more than one, the clients are assumed to be served by their closest facility, so the distance of other facilities are not important if there exists a close facility to a subset of $S$ not all of them. However, I need a ranking of facilities while they consider the sum of the distance to all nodes in $S$ for all $k$ facilities.

Example: 1st facility is the closest one to all nodes in $S$, 2nd is farther than 1st to all in $S$, etc.

The Floyd-Warshall algorithm computes all-pair shortest paths in $|V|^3$ time. Then you could compute the "shortest paths" from all nodes in $V$ to the subset $S$ by storing each shortest path in a $|V|$-size array, and sort these distances/array. First $k$ values will give you the $k$-nearest nodes.


Conditional branch instruction How is a conditional branch instruction implemented in hardware? The instruction checks the sign bit, how does it decide to load pc with the branch address or increment pc to the next sequential address?

A modern processor will first check whether it knows the value of the condition or not. For example, if you had a C statement "if (x / y > 3) ... " then it will take quite a while until the value of the ">" condition is known. If the condition is known, then the processor knows what to do.
If the condition is not (yet) known, then things get complicated. You don't want to wait until the condition is known. The processor will therefore use branch prediction to decide whether the branch is likely to be taken or not. For example, if this branch has been performed five times before, and each time the condition was true, then the processor will guess that the condition will be true again.
However, the guess might be wrong. Therefore all the following instruction are marked as "guessed", so the processor can undo the actions of each instruction. At the same time, the processor watches the condition: In the example, once the division x/y is complete, and the comparison x/y > 3 is complete and the condition is known, the processor will know whether the guess about the condition was right or wrong. If it was wrong, then the processor undoes all the effects of instructions that were performed but shouldn't have been. If the guess was right then the processor marks all the instructions back to "not guessed". One thing that cannot be undone is storing results to memory, so while the condition was guessed, nothing has been stored to memory. All those store instructions are now started.


Multi-processing cpu utilization estimate I find a formula on my book to estimate cpu utilization under multi-processing.

$ U = 1 - P^n $

U: cpu utilization
P: cpu idle

I want to know why or how to proof.

Edit:

The book is about operating system, not in english.

This may be like https://stackoverflow.com/questions/20328619/calculate-cpu-utilization/20328695?noredirect=1#comment88673153_20328695

I get an answer that is

  it's just basic probability theory

$P^n$ is the probability that all "cores" are idle simultaneously, hence $1-P^n$ is the probability that at least one core is in use.


Fast Consequence FInders I have been struggling in the search for a modern fast "consequence finder". That is, an implementation based on state-of-the-art theory; things of the ilk of Z3, Prover9, OTTER, etc.

To describe what I mean by "consequence finding" (and please correct my term usage if it's inappropriate):

Given a satisfiable and consistent set of clauses C, where a clause is a finite disjuction of literals, wherever there is some atom $p$ in some clause $\phi = p \lor \alpha$ and $\lnot p$ in some clause $\psi = \lnot p \lor \beta$, we add the new clause $\alpha \lor \beta$ to C (provided it cannot already be found in C). This is what I understand as the process of performing Resolution.

Assuming we generate all possible new clauses from C, contintually adding generated clauses, and trying to find new clauses again, we will have C'.

As a very small example, on the input:

$(\lnot p \lor q) \land (p \lor r)$

$(\lnot p \lor q) \land (p \lor r) \land (q \lor r)$ would be the output.

If we now remove subsumed clauses from C', i.e. clauses which are of the form $\alpha \lor \beta$ where there exists some other clause of the form $\alpha$, then we have a set of clauses C''.

I want C''. I was under the impression that there would be tools like those mentioned to generate this set since C'' is essentially what would remain when having performed vanilla resolution on a satisfiable set of clauses.

Updated answer, based upon the revised question:

It sounds like resolution does exactly what you want, so I suggest you implement the resolution algorithm (combined with a subsumption test). Implementing this is a straightforward programming exercise which should take you only a few hours.

Original answer to an earlier version of the question:

I don't know if there are any dedicated solvers aimed at solving this problem, but one "poor man's approach" might be to implement this using an off-the-shelf SAT solver.  The approach will depend on what you are looking for: in particular, from what space consequences are allowed to come from.

A useful building block

Let me first observe that you can use a SAT solver to determine whether a candidate clause is indeed a consequence or not.  This will be a useful building block below.

Suppose $\varphi(x)$ is a formula, on boolean variables $x=(x_1,\dots,x_n)$.  Let $c(x)$ be a clause.  You can easily use a SAT solver to test whether $c(x)$ is a consequence of $\varphi(x)$.  In particular, you test whether $\varphi(x) \land \neg c(x)$ is satisfiable; if it is satisfiable, $c(x)$ is not a consequence, otherwise $c(x)$ is a consequence.

Finding consequences that are conjunctions of literals

If you want each consequence to be a conjunction of literals, you can find the minimal consequence using a SAT solver.  In particular, it suffices to use dumb search.  Focus on clauses that contain a single literal; there are only $2n$ possibilities for them.  Test each of them to see which ones are consequences (if any); this requires $2n$ invocations of the SAT solver.  In other words, for each variable $x_i$, test whether $x_i$ is a consequence, and also test whether $\neg x_i$ is a consequence.

Now you have a bunch of consequences, say the literals $\ell_1,\dots,\ell_m$.  Then $\ell_1 \land \dots \land \ell_m$ is also a consequence -- and it turns out it is the minimal consequence (minimal, among the space of conjunctions of literals).  This procedure requires $O(n)$ invocations of the SAT solver, so it should be pretty efficient.

Finding consequences that are disjunctions of literals

If you want to consequences to be disjunctions of literals, it's also possible to find all minimal consequences (minimal, among the set of disjunctions of literals), though it is somewhat more complex.  Let me build up the ideas step-by-step:

Finding a single consequence. You can use a SAT solver to find a single consequence of $\varphi(x)$ (not necessarily a minimal consequence).  Feed $\neg \varphi(x)$ to the SAT solver, and let it find a satisfying assignment, say $x=\alpha$.  Then from this it is possible to identify a consequence (not necessarily minimal) of $\varphi(x)$.  In particular, the clause $x\ne \alpha$ is a consequence of $\varphi(x)$.  To put it another way, consider the clause $c(x) = \ell_1 \lor \dots \lor \ell_n$, where $\ell_i$ is either $x_i$ or $\neg x_i$ according to whether $\alpha_i$ is false or true; then $c(x)$ is a consequence of $\varphi(x)$.  This is a somewhat trivial and boring consequence, but it is a valid one.
Finding a minimal consequence. Once you have a single consequence $c(x)= \ell_1 \lor \dots \lor \ell_n$, it is now possible to to minimize it.  In particular, we will look for a minimal subset $S \subseteq \{1,2,\dots,n\}$ such that $c_I(x) = \lor_{i \in I} \ell_i$ is a consequence of $\varphi(x)$.  How do we do that?  We can simply try removing one literal at a time from $c(x)$ (removing one index at a time from the set $I$), testing at each step whether the result remains a valid consequence.  If removing a literal from the disjunction leaves it a valid consequence, go ahead and remove that literal; if after removal, it is no longer a valid consequence, then don't remove it.  Each test requires a single invocation to the SAT solver, so this procedure requires $n$ invocations of the SAT solver.  When you are done, you have a single minimal consequence $c_1(x)$ of $\varphi(x)$.
Finding another consequence.  Next, I will show to find a second consequence.  Let me explain using an example.  Suppose that $c^1(x) = x_1 \lor \neg x_3 \lor x_7$ (say), and suppose we know that $c^1(x)$ is a minimal consequence: no literal can be removed from this disjunction while keeping it a consequence.  We want to find a second minimal consequence $c^2(x)$ that is a disjunction of literals.  What can we say about the set of literals that appear in $c^2(x)$?  Well, either $c^2(x)$ does not contain the literal $x_1$, or it does not contain the literal $\neg x_3$, or it does not contain the literal $x_7$ (otherwise it would be a consequence of $c^1(x)$, i.e., subsumed, and thus not minimal).

So let's search for some consequence that satisfies these constraints.  One way to do this is to search for a satisfying assignment to $\neg \varphi(x) \land (\neg x_1 \lor x_3 \lor \neg x_7)$, by feeding this to a SAT solver.  Suppose the SAT solver gives us a satisfying assignment $x=\alpha$.  Then this immediately suggests a consequence that is not subsumed by $c_1(x)$, namely, the clause $x\ne \alpha$ (expressed as a disjunction of literals).  If we want, we can minimize this consequence to get a minimal consequence $c^2(x)$.  By construction, $c^2(x)$ will be minimal and different from $c^1(x)$.  This gives us a way to find two minimal consequences.
Finding all minimal consequences. Now it should be clear how to find all minimal consequences.  Suppose we have found $c^1(x),\dots,c^k(x)$, each of which is a minimal consequence of $\varphi(x)$, where $c^j(x) = \lor_i \ell^j_i$.  We define the formula

$$\neg \varphi(x) \land (\lor_i \neg \ell^1_i) \land \cdots \land (\lor_i \neg \ell^k_i).$$

Feed this formula to a SAT solver.  If it is unsatisfiable, you are done: you have found all minimal consequences.  Otherwise, suppose it finds a satisfying assignment, say $x=\alpha$.  Then this immediately supplies a  new consequence, which you can then minimize as above, to get a new minimal consequence $c^{k+1}(x)$.  Now you can iterate until there are no more to be found.

The running time for this algorithm is best expressed in an output-sensitive measure. If there are $m$ minimal consequence clauses, then this algorithm will complete after making $O(mn)$ queries to the SAT solver.  It might even be somewhat efficient, if you use a SAT solver that allows you to make multiple related queries and that remembers state across those queries.

Finding consequences that are in CNF form

Now suppose you want to allow consequences to be any CNF formula, and you want consequences that are minimal among the set of such consequences.  Then the problem becomes trivial.

In particular, $\varphi(x)$ is a trivial consequence of $\varphi(x)$, and it is possible to show that it is a minimal consequence: any other formula that has the same or more satisfying assignments is subsumed by it, and any formula that has fewer satisfying assignments is not a consequence.

A comment on resolution and on formulating problem statements

Resolution is just a means to an end, not an end goal in itself.  Resolution is one technique that is used in some SAT solvers, but SAT solvers also use other techniques as well -- and that combination of techniques is important.  What we've seen in practice is that current SAT solvers perform a lot better than vanilla resolution on many problems.

Therefore, my advice to you is to articulate the problem statement clearly, and try to keep clear in your mind the distinction between the goal (the problem statement) vs the way you'll achieve the goal (the algorithm you use).  Formulate the goal in a way that describes what you want to achieve, not how you want it to be achieved.  Once you articulate your goal clearly, you might find that resolution is not the optimal method.


How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms? How are asymptotical time complexities calculated for recursive algorithms?

Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they better taking time complexity into account? If they are better than non-recursive algorithms, then how are they better and why (not)?

Typically, by writing a recurrence relation for the running time and then solving the recurrence relation.  See How to come up with the runtime of algorithms? and Solving or approximating recurrence relations for sequences of numbers.   You might also want to read your friendly textbook and Is there a system behind the magic of algorithm analysis?.


What $O$ -symbol supresses? I am reading this book Asymptotic Methods in Analysis by N. G. de Bruijn. It describes the definition of $O$ symbol as

  A weaker form of suppression of information is given by the
  Bachmann-Landau O-notation. It does not suppress a function,
  but only a number. That is to say, it replaces the knowledge of a
  number with certain properties by the knowledge that such a
  number exists. The O-notation suppresses much less information
  than the limit notation, and yet it is easy enough to handle.
  Assume that we have the following explicit information

I don't under what does this means...

...That is to say, it replaces the knowledge of a
number with certain properties by the knowledge that such a
number exists...

Can anyone throw light on this passage of definition?
It will be a great help.
Thanks in Advance!

It’s trying to give an intuition and nothing more so, if the passage is not helpful to you, just skip it. Look at the actual definition instead.

Honestly, I think it’s a very bad and unhelpful attempt at giving intuition. In some ways, $\lim$ gives more information; in some ways, it gives less. In some senses, $\lim$ is more specific in that it gives a single value that the function asymptotically approaches, and the notion of limit makes sense approaching points other than $\pm\infty$.  If the limit is a real number, then saying $\lim_{n\to\infty}f(n)=c$ gives more information than $f(n)=O(1)$, which suppresses $c$.

On the other hand, for many functions we're interested in, $\lim_{n\to\infty}f(n)=\infty$ so $\lim$ gives almost no information.  In those cases, big-$O$ allows you to give more information.

I wouldn’t worry about the “suppressing a number” stuff. Saying $3x=O(x)$ suppresses the number three but $3x+1=O(x)$ suppresses two numbers, $3x=O(3x)$ suppresses nothing and $x=O(3x+1)$, er, un-suppresses stuff. Somethingl ike $x=O(x^2)$ is even less clear. It's hard to tell what de Bruijn really intended.


Complexity of deciding if a formula has exactly 1 satisfying assignment The decision problem

  Given a Boolean formula $\phi$, does $\phi$ have exactly one satisfying assignment?

can be seen to be in $\Delta_2$, $\mathsf{UP}$-hard and $\mathsf{coNP}$-hard. Is anything more known about its complexity?

Your problem is known as the $\text{UNIQUE-SAT}$ problem which is $\mathsf{US}$-complete. The problem is in $\mathsf{D^p}$ but not known to be $\mathsf{D^p}$-hard under deterministic polynomial time reductions, where the class $\mathsf{D^p} = \{ L_1 \cap \overline{L_2} \mid L_1,L_2 \in \mathsf{NP} \}$.

It was shown by Papadimitriou and Yannakis [1] that the set of uniquely satisfiable formulas is contained in $\mathsf{D^p}$. This follows by the definition of $\mathsf{D^p}$: let $L_1$ be SAT, and let $L_2$ be the set of formulas with $2$ or more satisfying assignments. Regarding $\mathsf{D^p}$-hardness of $\text{UNIQUE-SAT}$, Blass and Gurevich [2] gave a partial answer. For one, they showed a non-relativizing proof technique would be needed to settle the question. However, Valiant and Vazirani [3] gave a randomized polynomial time reduction from $\text{SAT}$ showing $\mathsf{D^p}$-hardness of $\text{UNIQUE-SAT}$ under randomized polynomial time reductions .

When it is known that the problem has at most one assignment or no assignments, the promise problem is called $\text{UNAMBIGUOUS-SAT}$. The Valiant–Vazirani theorem states that if there is a polynomial time algorithm for $\text{UNAMBIGUOUS-SAT}$, then $\mathsf{NP}=\mathsf{RP}$. To prove their theorem they showed that the promise problem $\text{UNAMBIGUOUS-SAT}$ is $\mathsf{NP}$-hard under randomized polynomial time reductions. A corollary that follows from the Valiant–Vazirani theorem is that $\text{UNIQUE-SAT}$ is complete for $\mathsf{D^p}$ under randomized polynomial time reductions.

[1] Papadimitriou, Christos H., and Mihalis Yannakakis. "The complexity of facets (and some facets of complexity)." Proceedings of the fourteenth annual ACM symposium on Theory of computing. ACM, 1982.

[2] Blass, Andreas, and Yuri Gurevich. "On the unique satisfiability problem." Information and Control 55.1 (1982): 80-88.

[3] Valiant, Leslie G., and Vijay V. Vazirani. "NP is as easy as detecting unique solutions." Theoretical Computer Science 47 (1986): 85-93.


Running time of CDCL compared to DPLL What's the complexity of Conflict-Driven Clause Learning SAT solvers, compared to DPLL solvers? Was it proven that CDCL is faster in general? Are there instances of SAT that are hard for CDCL but easy for DPLL?

Both CDCL and DPLL need exponential time in the worst case. I am not sure if it can be proved that CDCL is always faster than DPLL on every instance, but there is major empirical data suggesting it dominates. For a nice, short overview see the presentation Boolean Satisfiability Solving: Past, Present & Future by Joao Marques-Silva. He also has quite a few related talks online, see here.

CDCL is the dominating solver among all modern solvers. I would claim CDCL does indeed always dominate, and that is because it's basically a DPLL-based procedure, but with additional enhancements. It uses information gained during the search, restart strategies, special data structures, and so on.

There are instances that make all the known DPLL-like algorithms run in exponential time. For example, Alekhnovich et al. [1] exhibit such a family of 3-SAT instances. For more information on satisfiability, both theoretical and practical, I think one of the best sources are the Handbook of Satisfiability [2] and the regular International Conferences on Theory and Applications of Satisfiability Testing, known as SAT.

[1] Alekhnovich, M., Hirsch, E., and Itykson, D. Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. JAR, 35(1-3), 51-72, 2005.

[2] Biere, A., Heule, M., van Maaren, H. and Walsh, T. (Eds.). Handbook of Satisfiability. IOS Press, 2009.


What is the need for "some constant" times $n$? I have a question regarding the following sentence:

So we can make the following expressions:
The best case running time of LINEARSEARCH is a constant function $T(n)=a$ OR $Θ(1)$
The worst case running time of LINEARSEARCH is a linear function of $T(n)=an + b$ OR $Θ(n)$
Merging them together, the running time of LINEARSEARCH is no more than some constant times $n$

There is reference to some constant, what is the point of this constant? Why is not just that the running time is $n$?
What is the some constant and why does it need to be taken into consideration?

What is the running time of an algorithm? To answer this question, we need to specify an exact computation model with a cost for each operation. Whatever computation model you choose to use, it is highly unlikely that the running time of an algorithm on an input of size $n$ is exactly $n$. It is far more likely to be of the form $an+b$ for some constants $a,b$, and even more likely to vary a bit with the exact input, but to be bounded by some expression such as $an+b$.
As an example, consider the following algorithm for computing the maximum of an array $A[1],\ldots,A[n]$:
max = A[1]
for i = 2, ..., n:
  if A[i] > max:
    max = A[i]
return max

Let us convert it into "machine instructions":
      max = A[1]                 (1)
      i = 2                      (2)
LOOP: if i>n, jump END           (3)
      if A[i]≤max, jump CONT     (4)
      max = A[i]                 (5)
CONT: i = i + 1                  (6)
      jump LOOP                  (7)
END:  return max                 (8)

Let's assume that each line costs $1$ time unit (this is a quite arbitrary assumption). How much time does the algorithm take on an input $A$ of length $n \geq 1$?
Lines $1,2,8$ run once. Line $3$ runs $n$ times each. Lines $4,6,7$ run $n-1$ times each. Line $5$ runs once per "left-to-right record" of $A$ beyond $A[1]$, which can be any number of times between $0$ and $n-1$. In total, the running time is between $3+n+3(n-1)$ to $3+n+4(n-1)$, that is, between $4n$ and $5n-1$.
If we choose a different cost model, we will likely get a different running time. However, this running time will likely still be $O(n)$. This is why big O notation is so useful – it hides such details.


Can we write a program that can say if any 2 given programs do the same w.r.t input - output pairs I'm new to theoretical CS research. I have the following question: Given 2 different computer programs, each generating certain outputs for a given set of inputs. Assuming we are given the range of values for input variables (i.e., min to max values), is it possible to check with another program whether these 2 programs will give the same output values for all possible input values, without actually running the 2 programs for all input values?

Thanks.

No.  That's undecidable.  Suppose the first program is

return 42

and the second program is

if (f(x) halts)
    return 0
else
    return 42

where x is the input.

Do these two programs yield the same output, for all possible inputs?  That depends whether f always halts on all inputs.  And that is exactly the halting problem, which we know is not decidable.  It's easy to see that, as a consequence, this problem can't be decidable either (if it were, you could decide the halting problem).


Hamiltonian path in directed graph Let G be a directed graph such that every two vertices are connected by a single edge.
How do I proof that such G has an hamiltonian path?

Proof by induction
Basis. All complete oriented digraphs with two vertices have Hamiltonian path - it's obvious.
Induction step. Let's assume that complete oriented digraph $G_{n-1}$ with $(n - 1)$ vertices contains Hamiltonian path $(s, ..., t)$ from vertex $s$ to vertex $t$. We'll show how to build Hamiltonian path for complete oriented digraph $G_n$, which is constructed from $G_{n-1}$ by adding a vertex $p$.
Case 1. The $G_n$ has an edge $(p, s)$. The Hamiltonian path in $G_n$ will be $(p, s, ..., t)$.
Case 2. The $G_n$ has an edge $(s, p)$. Then we need to scan the Hamiltonian path $(s, ..., t)$, trying to find an edge $(v_{i-1}, v_i)$, such that the graph $G_n$ contains edges $(v_{i-1}, p)$ and $(p, v_i)$. There are two subcases:
Subcase 2.1. We can find such a pair - then the new Hamiltonian path will consist of three parts - $(s, ..., v_{i-1})$, $(v_{i-1}, p, v_i)$ and $(v_i, ..., t)$.
Subcase 2.2. We can't find such a pair - it means, that all the edges from vertices on the path $(s, ..., t)$ to the additional vertex $p$ are oriented to this vertex. The new Hamiltonian path will be $(s, ..., t, p)$.


Why is the Mean Time To Failure of multiple disks calculated via division and not multiplication? I am reading about disk redudancy.
I read the following:

  Suppose that the mean time to failure of a disk is 100,000 hours. Then
  the mean time to failure of some disk in an array of 100 disks will be
  100,000/100 = 1000 hours

I don't understand this. Why isn't it 100,000^100 instead?
Then the same textbook says in the next paragraph concerning 2 mirrored disks:

  If the mean time to failure of a single disk is 100,000 hours and the
  mean time to repair is 10 hours then the mean time to data loss is
  (100,000^2)/2*100

Now here it multiplies for the 2 disks but before the MTTF was divided.

Can anyone please help me figure out how we calculate this.
In case it matters the text book is Database Concepts from Silberschatz 4th edition paragraph 11.3.1 (Improvement of reliability via redundancy) page 403

Think of it this way. A single disk fails on average after $100,000$ hours. Now you have $100$ disks. How long before one of them fails? It will almost certainly take much less than $100,000$ hours for the first to fail, and much more than $100,000$ hours for the last to fail. (This of course depends on the distribution of failures, which is assumed to be exponential here.)

Here is another example: if you keep throwing one die, it will show $6$ after an average of $6$ throws. Now suppose that you throw two dice. How long do you expect to wait until some $6$ shows up? Certainly less than $6$ throws. (In fact, $36/11 \approx 3.27$ throws on average.)

In the second example, you need both disks to fail in order for data loss to occur. Not only this, but you also want both failure "events" to be within $10$ hours of each, since otherwise the system will recover after repairing the faulty disk. Hopefully the book explains the calculation somewhere, if not, the book is useless and you should tell your instructor to use a different one (perhaps with less pictures but more content, and not $n$th edition, prepared to finance the publisher's new yacht).