Logic Gates in circuits We can make all the gates using nand or nor gates. My teacher told us that nand gates are cheap too, then why do we need other gates at all?

They logically exist, you can not un-invent them. Even if no one ever made one, they would still exist in your mind.
If is easier to say “open door if I want to go through door or you want to go through door” than to say “open door if I don't want to go through door nand you don't want to go through door”
An alternate question — Why do we build devices with just one gate? i.e. nand or nor?
We do this because it makes the electronics simpler, if all the devices are the some, as we only have to implement one type of gate. This is about simplicity of the device, not of the logic (as this could be a bit more complex). This logical complexity could push the size up, but the symmetry of all gates being the same pushes the size down. Also a lot of the logical complexity can cancel out.
A similar question — Why do we have multiply in maths. When we can do everything with addition?

Why do we have addition when we can just use increment: 3+4 = 3+1+1+1+1
Why do we have multiplication when we can use addition: 3×4 = 3+3+3+3
Why do we have exponentiation when we can use multiplication 3⁴ = 3×3×3×3

If you were to continue to look inside the computer, then you will see that it is,some what, like this:

transistors → nand or or
nand or nor → all logic gates
logic gates → addition
logic gates → flip flops
flip flops → shift registers → multiply by 2
multiply by 2 & addition → multiplication
…

Why do we have steel, when you can just have iron, carbon, cobalt … ?


Maximum Subsequence Sum : Mark Weiss: In the highlighted part below how is Weiss concluding that the array starting at an arbitrary index "p" and ending at "j" can never be larger than the array starting at "i" and ending at "p-1"?

By his own example (the inner loop of algorithm 2 shown below) this is demonstrably false.

Let i = 0, and j = 3.

Let a[ 0 ] = -14, a[ 1 ] = -4, a[ 2 ] = -2, a[ 3 ] = -1.

If p = 2, the subsequence sum from "p" to "j" is clearly bigger than "i" to "p-1".

Even more concerning is Mr. Weiss seems to pull an assumption out of thin air ("j is the first index that causes the subsequence starting at index i to become negative") when nothing in the above could possibly imply that! Indeed, Weiss only mentions "detection" of the subsequence sum being negative between index "i" and "j", but never where the source of this could only occur. Where is this coming from?

Thanks for any help!

I think you are confused about which algorithm he is describing. His description isn't for algorithm 2 but for algorithm 4, where an imaginary index i in reintroduced.

Let me write this algorithm with this index to make it clear to you:

maxSubSum(array a):
  maxSum = 0, thisSum = 0;
  i = 0;
  for j going from 0 to length(a)-1:
    thisSum += a[j];
    if thisSum > maxSum:
      maxSum = thisSum;
    else if thisSum < 0:
      i = j+1;
      thisSum = 0;
   return maxSum;

Now you can see that in this algorithm, whenever thisSum < 0, then j is indeed the "first index that causes the subsequence starting at index i to become negative", and the rest of the claim follows. Notice in particular that the example you gave cannot occur with this algorithm (you will never have i=0 and j=3 in that case).


Ford-Fulkerson algorithm clarification In the second edition of the book of Cormen "Introduction to Algorithms" appears the following example (in the left part is the residual network while in the right part shows the flow results):

I have a problem understanding the part (c). The augmenting path is $s\rightarrow v_2\rightarrow v_1\rightarrow v_3\rightarrow t$ with a minimum weight of 8. This weight should be added or decreased in the right part of b:

$s\rightarrow v_2$: it was 0 by default, so now it has 8/13

$v_1\rightarrow v_3$: it has 4/12 adding 8 we would have 12/12

$v_3\rightarrow t$, it has 7/20; adding 8 holds 15/20

the problem is in the vertices: $v_1\rightarrow v_2$, for what I see it has only capacity 4 (b right part), so how to put the flow of 8 that it needs the procedure?. I see that at the end we finish up with a $v_1\rightarrow v_2$ with a value of 1/4, but I have my doubts how to get that result.

Is it that because $v_2:v_1$ has only capacity of 4, and I should put 8 of flow, that only 4 units pass through $v_2:v_1$ and the remaining 4 goes back from $v_1:v_2$? In that case it finds a value of 7/10; so it needs only 3 units giving us $v_1:v_2$ equals to 10, and because there is 1 unit remaining that goes from $v_2:v_1$ giving us 1/4?

Is that logic correct?

Prior to step (c) there are 7 units flowing from $v_1$ to $v_2$. The augmenting path pushes 8 units of flow from $v_2$ to $v_1$: 7 of these cancel the existing flow from $v_1$ to $v_2$, and 1 unit now flows from $v_2$ to $v_1$.

More generally, the residual network shows you how much flow you can push in each direction. The edge $v_2 \to v_1$ has a capacity of 11, so you can push up to 11 (=7+4) units in this direction.


How CPU know which process generated an interrupt? When a computer OS supports multi-program, it needs to have a scheduling algorithm to handle which process will be run by the cpu.

If a process is in state 'blocked' waiting for IO, the scheduling causes another process to be taken by the cpu while the process in state 'blocked' is waiting for a response I/O. In this situation, when the process returns to state 'ready' and then runs, how does the cpu know which process to run and where it was stopped ?

First of all, different environments need different scheduling algorithms.

This is mainly because different operating systems have different objectives according the needs. Then, what the scheduler is going to optimize will not be the same for every case.

There are Real time systems, batch processing, interactive systems, etc. Let's consider interactive systems because these are the typical desktop computers and servers, offering services for various users. The main concerns for the scheduler is to "quickly" answer users querys.

In general, the scheduler tells the CPU wich process is next (the CPU is driven by the scheduler), and the details depends on the sheduler algorithm.

Consider the following simple and old scheduling algorithm, called Round-robin:

Each process is assigned with a pre-fixed quantum of time. There is a list of process. The CPU run process A, when the time is over (or A is blocked before time) it switch's to the next process B in the list. A is moved to the end of the list. The context of A is saved in the Process Control Block, so in the next turn for A the CPU knows where to continue because the IP register was saved in that context.
In this case, is like all processes have the same priority.
One key thing here is how much time is assigned to the quantum, it must be a reasonabe amount of time.

There are more complex algorithms, based in priority scheduling. In general, there are different classes of hierarchys, and each hierarchy may have his own queue of processes waiting to run. The CPU can start running process of the highest priority class, and when that class is empty it move downwards the hierarchy. The time of execution in this case can be a quantum, or the CPU can decrease priority of the current process in each clock interruption to avoid indefinite postponement of the other processes.


Using Dijkstra's algorithm with negative edges? Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance has been found. However since negative edges can reduce the distance, a future shorter distance might be found; but since the node is deleted it cannot be updated.

Wouldn't an obvious solution to this be to not delete the node? Why not keep the node in the queue, so if a future shorter distance is found, it can be updated? If I am misunderstanding the problem, what is preventing the algorithm from being used with negative edges?

Short answer is that Dijkstra is a greedy algorithm, meaning we assume that we have made the best choice possible in every step of the algorithm. With negative edges, this is no longer possible and thus a greedy algorithm will not suffice.

Here's an analogy: (that might help, or confuse even more) Take a convex optimization problem and poke a concavity into it. Now ask the question why it can't be solved with a linear program. The problem is that the linear program's premise is that once we reach the edge of a convex surface in the direction of optimality, we know for certain it is optimal. With a concavity, this no longer works and the algorithm falls flat. The negative values are like these concavities, they introduce local extrema making it harder to find the global one.


How hash-table and hash-map are different? In the context of CS, how the hash-table and hash-map are different?

I was watching a part of "Algorithm with Swift" video in Udacity, and I discovered the terms "hash-table" and "hash-map" are somewhat confusing.

As far as I understand,

hash table → stores keys only → Swift Set.
hash map → stores key/value pairs → Swift Dictionary.

But, Wikipedia is talking hash-table is same thing with hash-map. Here I could not find any help.

Is this formal or widely accepted CS term? Am I understanding correctly? If I'm wrong, please correct me. Thanks.

I know industry uses their own terms that can be different, and I am asking about academia because I believe terms are more consistent in academia. If it's not, I just would abandon to learn academic terms.

If you ask me, you're correct and Wikipedia is wrong, as the complaints on the article's talk page (some 11 years ago!) clearly explain, but it was never fixed (or it was fixed and reverted).

A hash table stores items; these items can be keys (in which case it implements a set), or key-value pairs (in which case it implements a map, i.e. a hash map), or perhaps something else, e.g. triples; the Wikipedia article describes only the key-value case, while I was only taught the key-only case in class.

Some people do use hash table to mean hash map, so Wikipedia successfully describes a particular usage of the term; it should also describe the other cases. (It does describe how a hash map can be used to implement a set and other data structures, but that's not the same thing.)

In IT, most terms mean different things to different people, and most people using the term in one sense aren't aware that other people use it in another sense; hash table is no exception.


Array search NP completeness Given an unsorted array of size n, it's obvious that finding whether an element exists in the array takes O(n) time.

If we let h = log n then it takes O(2^h) time.

Notice that if the array is sorted, a binary search actually takes O(h) time (which is polynomial) but the binary search cannot apply to an unsorted array.

Is it possible to prove that the problem to find an element in an array (yes or no) is NP complete in terms of h. What problem should I reduce from and how to reduce?

A more formal definition of the problem is given below.

We have an oracle, which is a binary tree of height h with each node having random values. I.E. a tree that DOES NOT have the property that all values in the left subtree of a node must be smaller than the value in the node or all values in the right subtree of a node must be greater than the value in the node. However all nodes in the oracle tree are guaranteed to have value between 0 and 2^h-1.

  The input is a number to be searched. The input is guaranteed to have value between 0 and 2^h-1. (The input has h bits)

(Let's say we are searching through the same array every time and hence we have the same oracle every time so the tree itself is not a part of input.)

  The output is YES or NO, indicating whether the input is in a node of the tree or not.

Question: whether this problem is NP complete or not in terms of h. This problem is NP because if a path to the YES node in the tree is given it can be verified in O(h) time.

Assuming NP != P, since the problem is in NP it must be either NP-complete or P (Apparently there is something called NP-intermediate (credited to Nicholas) so that's another possibility as well).
If it is NP-complete, what problem can be used to reduce to this problem?

Note that if the oracle tree has the property that left subtree of a node is less than the node and right subtree of a node is greater than the node then the problem is in P and NOT in NP complete because binary search can be applied.

Intuitively, this problem can be viewed as a non-deterministic turing machine and every single possible path needs to be considered but this intuition cannot be used to "prove" the problem is NP complete. I want to know if we can reduce any known NP-complete problem to it.

Reference: (Original Post)
https://stackoverflow.com/questions/28847966/array-search-np-complete

If you want to prove that a problem is NP-complete, you don't get to make up your own definition of NP. NP is the class of problems that can be solved by a nondeterministic Turing machine in time bounded by some polynomial function of the length of the input.

Specifically, you don't get to use oracles, you don't get to use some other measure of the size of the input (e.g., the logarithm of its length) and you don't get to make random access to the  contents array: you have to walk the head of the Turing machine there, one cell at a time.

Your problem is, as you say in your first sentence, clearly in P. It is, therefore, very unlikely to be NP-complete, since that can only happen if P=NP.


Macros vs lazy evaluation in scheme inspired language I'm writing a simple scheme inspired interpreter. I'm not calling it a scheme implementation because I don't really want to implement all the standard, only the minimal set of primitives needed to keep evolving it from it self.
I have two primitives lambda and lazy, lazy is a lazy version of lambda in the sense that it receives its arguments unevaluated and it can chooses on what evaluate
Here are both as examples:
(define foo (lambda (x) (+ 1 x)))

(define foo (lazy (x) (+ 1 (eval x))))

The idea to have lazy is not needing macros (at last in the core language, I may implement it afterwards on top of lazy).
My question is, given lazy do I need macros/hygienic at all? Isn't this primitive a lot clearer than macros? What kind of macros I can't define on top of lazy and why?

If lazy only gives you the option of either evaluating or ignoring each argument, then you can't implement macros like cond with it, since neither ignoring the predicate of a (pred expr) argument nor calling it as a function is the right thing to do. If lazy allows you to inspect the arguments in other ways then it essentially is a macro system.
If you want your language to support compilation then you'll have to put limits on where lazy can appear, or else pay a significant code size and efficiency penalty for every application of a function that can't be identified at compile time. If the language is purely interpreted then you don't really have that problem, but you still may want to think about the implications of allowing callers to inspect the implementation details of functions by passing lazys to them where they expect lambdas.


What if the electricity goes off while a file is being renamed? Suppose I'm renaming a file and the electricity goes off right in the middle. Naively, it looks like the file could be in some “half-renamed” state. Maybe the name would have half the old name and half the new name. Or maybe the file could disappear altogether because it no longer exists under the old name but it doesn't exist yet under the new name.

How can a filesystem protect against loss of power while a file is renamed? Are these just theoretical techniques or are they used in practice?

Most filesystems and filesystem implementations are designed to be resistant to a loss of power. When you rename a file, with most operating systems, you can expect to always see the file either under its old name or under its new name. If there is any intermediate stage where the file is so to speak half-renamed, the operating system will hide it from you, even if the machine crashes at a bad time. Renaming a file (with most filesystems) is an atomic operation.

The precise method for ensuring atomicity varies from filesystem to filesystem and may also depend on other system components such as the storage hardware and the disk driver. In this answer I'll describe some common techniques at a high level. If you look at an actual filesystem implementation, you're likely to find that things are a lot more complicated.

Most storage media guarantees that writes are atomic at the level of a block. A typical block size is 512 bytes. This is often guaranteed by the disk firmware. Here are some common techniques for noticing or preventing data corruption due to a power failure:

One possibility to protect against power failures is to have a small power reserve that is sufficient to complete the writing of the current block.
Another method is that the disk stores the block content followed by a checksum of the block: if the new content of the block is only half-written, the checksum will be wrong, and the block content is lost but the operating system will not re-read bad data.
A third method is to maintain a dirty bit: flip it from 0 to 1, do the actual write, then flip the bit back to 0, so that if the dirty bit is 0 then the block content is known to be good.

Let's assume for a moment that the file name is stored entirely within one block. Then what the filesystem driver needs to do to rename the file is to update that block with the new name.

If the storage medium guarantees that block writes are atomic, then the filesystem driver simply writes the new block content. If the write goes through, the file will have its new name; if a power failure happens, the file will retain its old name, meaning that the power failure effectively happened before the instruction to rename the file was carried out.
If writing a block may damage it, the filesystem driver creates a new block with the new name. Once that block has been successfully created, the filesystem driver updates the “parent” block that contains the location of the block containing the name to reflect the new location. The location of the parent block must be updated in its parent and so on.
Such a chain has to stop somewhere. One way to stop is to have a block with two possible locations L1 and L2. Maintain a version number for the block, stored inside the block. Increment the version number each time the block is written. At any time, whichever of L1 and L2 has the highest version number is the real location.

In general renaming a file may involve rewriting several blocks. The filesystem must take care in which order these blocks are written. For efficiency, it is often useful to reorder writes. This is often a consequence of caching and buffering: blocks are not actually written to disk each time they are modified, but kept in memory for a little time in case they are modified again. Another reason to reorder writes is that it's more efficient to group consecutive writes together (write block 42 then 43 then 44, even though 43 was modified first, then 42 then 44). The management of this reordering is a very complex part of typical filesystems, because it is very important for both correctness and performance.

One method that is used by many modern filesystems is journaling (in the database world, this is called a log). In addition to the actual data blocks, the filesystem maintains a list of operations that it performs. These operations are stored in strict chronological order. The journal consists of a list of records such as “rename the file from oldname to newname, affecting blocks B1, B2 and B3”. If a power failure interrupts the writing of a journal record, the operation hasn't taken place. The information in the journal duplicates the data which is written as performance permits. If the data isn't written at its final location due to a power failure, the operating system performs a journal replay at boot time: it reads the journal entries, checks whether each operation has taken place and performs the operation if necessary. The operating system also periodically marks journal entries as completed once it knows that the data has been successfully written. In many filesystems, this allows old journal entries to be erased, so that the journal keeps to a fixed size. There are even filesystems that consist solely of a journal, so that a file is defined by pointers to older journal entries that write its contents — this isn't very common though.


1-to-1 cryptographically secure bit shuffling Given an input item (N bytes), I'm looking for a function that will map this to an output (still N bytes).  The function should have the following qualities:

It should be 1-to-1 so that all inputs map to some output and so that no two inputs map to the same output.
Given an output element it should be difficult to guess the input that lead to that output, even when the mapping is completely known.

Does such a function exist? Where can I learn more?

This is known as a one-way permutation.  The "permutation" refers to the first of your two requirements; the "one-way" refers to the second of your two requirements.  There are various candidate constructions for one-way permutations, e.g., based on raising to the third power modulo an RSA modulus or other schemes.


How to get initial flow for TSP with missing edges I need to solve a version of the traveling salesman problem with missing edges. I've decided to use simulated annealing.

How do I generate a valid initial path effectively?

I would use a greedy algorithm, but I can't be sure it will result in a valid path. I could still use it and hope that simulated annealing will find a valid path, but I can't guarantee that it will.

Set the cost on the missing edges to $+\infty$, or some suitably large constant.   Then all paths are valid, and you can apply simulated annealing.  Simulated annealing will have a very strong incentive to avoid those edges.

In general, you cannot expect any algorithm to both (a) be guaranteed to find a valid path, and (b) be guaranteed to terminate in a reasonable amount of time.  That's because finding a valid path is the Hamiltonian path problem, which is NP-hard -- so even finding a single path could be extremely hard, depending on the input graph.  Since you presumably want an algorithm that terminates in a reasonable amount of time, that means you'll have to accept the possibility that the algorithm fails to output a valid path.  (If not, then you'll have to accept the possibility that the algorithms fails to terminate in your lifetime, which seems just as bad.)


Implications of $NP = \Sigma_2 P$ for PH collapse A simple fact is that $P = NP \to P = coNP$, which follows from the observation that $P$ is closed under complement.

I am having trouble seeing that an analogous statement is true at higher levels of $PH$.  For example, is it known that $NP = \Sigma_2 P$ implies $NP = \Pi_2 P$?  If so, is there an easy proof?  Would such a statement have any other interesting implications (For example $NP = coNP$)?

It seems somewhat likely to me that this is true, based on the observation that $NP = \Sigma_2 P$ means that $\exists \forall$ quantifier patterns can be replaced with $\exists$ quantifier patterns, and so all higher levels of $PH$ would at least collapse to $\Pi_2 P$.

The answer is yes.
notice that $NP=\Sigma_1$ and for all $i$ you have $\Sigma_i=\Sigma_{i+1} \Rightarrow \Sigma_i=\Pi_i$. This is true since $\Pi_i\subseteq \Sigma_{i+1}=\Sigma_i$. The inclusion holds since if $\bar{L}\in\Sigma_i$ then you have $x\notin L \iff \exists v_1\in \left\{0,1\right\}^{p(|v_1|)}...Q_iv_i\in\left\{0,1\right\}^{p(|v_i|)}M(x,v_1,...,v_i)=1 $ or equivalently $x\in L \iff \forall v_1\in \left\{0,1\right\}^{p(|v_1|)}...\bar{Q_i}v_i\in\left\{0,1\right\}^{p(|v_i|)}M(x,v_1,...,v_i)=0$. So now your $\Sigma_{i+1}$ verifier for $L$ will ignore $v_1$, run $M(v_2,...,v_{i+1})$ and flip the answer. It remains to show $\Sigma_i\subseteq\Pi_i$. Let $L\in\Sigma_i, \bar{L}\in \Sigma_{i+1}$ and since $\Sigma_i=\Sigma_{i+1}$ you get $\bar{L}\in\Sigma_i$.

Back to your question. If $NP=\Sigma_2$ (or $\Sigma_1=\Sigma_2)$ then $\Sigma_1=\Pi_1$. Let $L\in\Pi_2$ then $\bar{L}\in\Sigma_2\Rightarrow \bar{L}\in\Sigma_1\Rightarrow \bar{L}\in\Pi_1\Rightarrow L\in\Sigma_1$, So $L\in NP$ as required. The opposite direction is clear(for all $i$ $\Sigma_i\subseteq\Pi_{i+1}$).


Algorithm for winning solitaire Is there an algorithm that could check whether it is possible to win in the current situation in solitaire? That is, can we remove all cards from the table in a certain number of moves?
Description of the game:
Two decks of cards (36 pieces each) are connected and shuffled, and then they are laid out in 8 piles of 9 cards each. Possible work only with the top cards in each of the piles, namely, transfer one or several consecutive cards of a lower value to a card of a larger one (suits are not taken into account). If there are 9 cards in one of the piles in the correct order (ace-king-queen-jack-10-9-8-7-6), then this set is removed. If all the cards are removed from one pile, it can still be used and any card can be placed on top

There sure is. Some sort of backtracking program will do the job. If you want the minimal number of moves, perhaps the (memory expensive) way to go is breadth first search. Maybe you can squeeze some performance out of it by adding conditions to cut off impossible branches or stop expanding when the current path is longer than the current best, or heuristics to search more promising moves first.
The eight queens puzzle is the typical example of backtracking in a much simpler setting, the cited page has a sample Pascal program (readable enough for any C-savy person). Dijkstra wrote a highly detailed discussion of the program, see his "EWD316: A Short Introduction to the Art of Programming".


Is there an algorithm for algorithms time/space complexity optimisation? In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of algorithms?

For example an implementation of bubble sort as an input for such an algorithm would produce an implementation of a sorting algorithm with time complexity closer to $O(n\log n)$.

Look up Blum's speedup theorem (yes, this article is less than informative; look at a book on complexity theory). It essentially says that there are programs for which there is a program doing the same job that is faster by any specified margin for almost all input data.

By Rice's theorem, it is impossible to know if two given programs do the same job.

Yes, for some very restricted notions of "program", given an example one can construct the "best possible" program for the job. Important classes, even. But a very far cry from anything which is able to express bubblesort.


Application of a directed almost tree Is there anything interesting to say about an "almost BST" with directed edges?
Is there a domain where this structure naturally arises? I'm imagining a tree like the one below, but it would of course be more interesting if the tree were deeper with just a few of these strange edges.

I found this article on circuit rank which uses the term "almost tree", but it talks about circuits in undirected and directed graphs. What I'm describing is not a cycle.

What you are looking for are directed acyclic graphs (DAGs). If you want your DAG to have a unique "root", then you can ask for a DAG with a single source. DAGs are very useful in many branches of computer science.


How to read $NC^1\subset L \subset NL \subset SAC^1$, $SAC^1=LOGCFL/poly$, and similar statements? The (complexity zoo) description of $NC^1$ says that it is contained in $L$, i.e. $NC^1\subset L$. The description of $SAC^1$ says that it is equal to $LOGCFL$$/poly$, i.e. $SAC^1=LOGCFL/poly$.

The wikipedia article on $LOGCFL$ says that it is situated between  $NL$ and $AC^1$. I read this as $NL\subset LOGCFL\subset LOGCFL/poly=SAC^1\subset AC^1$, hence $NL\subset SAC^1$.

Obviously $L\subset NL$, so we get the nice summary
$$NC^1\subset L \subset NL \subset SAC^1$$

But the statement $SAC^1=LOGCFL/poly$ makes me wonder, whether $NC^1\subset L$ or rather
$$NC^1\subset L/poly \subset NL/poly \subset SAC^1$$

Honestly, I'm really unsure now. So I googled a bit, and found lecture notes introducing Boolean circuits with even more doubtful statements

  The usual convention is not to count "not" gates in either of the above: one can show that all the "not" gates of a circuit can be pushed to immediately follow the input gates; thus, ignoring "not" gates affects the size by at most $n$ and the depth by at most $1$.

I heavily doubt that this statement is "exactly" true. I feel reminded of the wikipedia article on Fagin's lemma, and similar "sloppy CS statements". But how am I supposed to read such sloppy statements, and how can I guess what they are intended to mean?

The source of the confusion is probably uniformity. A circuit class like $\mathsf{NC}^1$ can be defined in two different ways:

Languages computed by bounded fan-in circuits of polynomial size and logarithmic depth.
Same as 1, only the circuits are uniform: there is an efficient Turing machine that on input $1^n$ generates the $n$th circuit.

The definition of uniformity is vague since there are several different definitions, many of them fitting the above description (with different definitions of efficient). The classic paper On uniformity within $\mathsf{NC}^1$ shows that many of these definition are in fact equivalent, and as far as I know, their common definition remains popular today. It often goes by the name "$\mathsf{AC}^0$-uniform".

If you want $\mathsf{NC}^1 \subseteq \mathsf{L}$ then you need the uniform version of $\mathsf{NC}^1$. If you want $\mathsf{NL}/poly \subseteq \mathsf{SAC}^1$ then you need the non-uniform version of $\mathsf{SAC}^1$.


Concrete example of Vertex Cover to Subset Sum reduction In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem, mostly to prove Subset Sum is NP-Complete. I also see a reduction in the line of - A graph G has VC of size k if and only if there is a subset S that sums exactly to t. However, not able to find out (understand) exactly what is this t. I think providing a concrete example will help many like me. Request any one to provide a concrete graph with |VC| 3 or something manageable, and then show exact value of t i.e. what would be the exact instance of subset sum problem. Finally, explaining/clearly mentioning elements of S would be of great help.

In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem...

We do?

  ... mostly to prove Subset Sum is NP-Complete.

There's no particular reason to go down that route. Karp [1] defined the Knapsack problem as: given $a_1, \dots, a_r, b\in\mathbb{Z}$, is there a set $S\subseteq \{1, \dots, r\}$ such that $\sum_{i\in S}a_i=b$? This is one variant of what is now called Subset Sum. If you prefer to define Subset Sum such that $b$  is always zero, we'll come back to that in a minute.

Karp shows that Subset Sum is NP-complete by the chain of reductions
$$\text{SAT}\leq \text{3SAT} \leq \text{Chromatic Number}\leq\text{Exact Cover}\leq\text{Subset Sum}\,.$$
In particular, the reduction from Exact Cover to Subset Sum produces an instance where the $a_i$'s and $b$ are all positive so, if you want to define Subset Sum as "is there a subset whose total is zero?", you can set $a_{r+1}=-b$.

Since Subset Sum and Vertex Cover are both NP-complete, there is clearly a reduction between them. However, you shouldn't expect that there's a "nice" reduction where a small VC instance naturally transforms into a small Subset Sum instance that makes you say, "Aha, now I understand." And that applies to most pairs of NP-complete problems.  In complexity theory courses, we teach the simple, intuitive reductions, usually between problems that are somehow similar, or between SAT or 3SAT and a problem that isn't about Boolean formulas. That can give the impression that there's a natural reduction between any pair of NP-complete problems; in reality, there usually isn't.

[1] Richard M. Karp, Reducibility among combinatorial problems. In Complexity of Computer Computations, Plenum Press, 1972. (PDF)


Role of network layer in Routers I just started reading communication networks.
Now, routers contain the network layer, data link control layer and physical layer.
That being true I am confused as to why the network layer is required or to be more specific what is its function.
In "Computer Networks A top-down approach", it is written that the network layer inspects the datagram header to look at the source and host addresses and then passes the datagram to the data link layer of the next link for it to decide where to pass the data packet to.
                Network layer does not seem make any changes to the headers associated with the data packet or modify the headers in any way.
This begs the question, what does the network layer then do???

There are only three high level abstractions in the network stack.

Link Layer: Knows how to transfer data (physically*) across one hop. This layer with deals encoding and framing bits, controlling channel access, detecting and recovering from collisions in the transfer medium. Eg: Ethernet, WiFi etc.

Network Layer: Does forwarding and routing (note: they are different procedures). Knows how to forward a packet to the destination. Has a table of IP-->link mapping. Let's assume your router/switch has three links, it decides (and only knows) which link to take to get closer to the "destination IP". Delegates the physical mechanism of transferring bits on that link (which may be Ethernet or WiFi or whatever) to the link layer. Once your router finds that the "destination IP" matches "your IP" it makes an up-call to the End to End layer, i.e, no more links have to be traversed. Eg: Internet Protocol IP. Just to be concrete, a router has a forwarding table which has the following form,

Forwarding Table
IP address   Link to take
"Your IP"    E2E layer
127.35.*.*   link 2
10.*.*.*     link 3
173.*.*.*    link 1

These individual links may be Ethernet or WiFi or DSL etc. Note: an intermediate gateway/switch may not have E2E layer implemented.

Packets in the network layer may get dropped due to congestion, link failures or may not reach destination due to a wrong route.

The links layer and the network layer taken together is just a "BEST EFFORT" dumb network, that doesn't guarantee: ordered delivery, delay limits, congestion control or any form of reliability that a practical application might require. It tries its best to take the packet through but it is not assured. It does not guarantee end to end delivery.

To answer your question, packet routing is in itself a hard problem which requires implementing an abstraction called the network layer for this purpose. Look for "Path vector routing", "BGP" to understand how network layer prepares these forwarding tables.

End to End Layer: This builds on top of the network layer, requests re-sending of lost messages, acknowledgments, arranges out of order segments, manages resources like timer etc. It works to ensure, whatever the sender sent has arrived intact. Eg, TCP, UDP

*Link layer doesn't always mean physical transmission, for details, read about recursive network stacks like Gnutella


When using a hash and a collision occurs and linear probing is used how is that item found again How is the search for the item supposed to find the specific item if the data is all clumped together and all the search is given is the output of the hash function. I don't understand how it knows which of the pieces of data is the one that corresponds to the key if linear probing has been used so it could be any of a number of pieces of data?
Thanks for any help

Any given equality function over the objects.  You're asking if an object is in a hash table, and it is if there is an object that is "equal" to the given object.

And remember that object equality implies hash equality.


Reducing Zero-One Integer Linear Programming problem to SAT I want to find a reduction from Zero-One Integer Linear Programming problem to Boolean Satisfiability problem (SAT), that is, to find a polynomial-time transformation $T$, such that:
$$IP \leq_P SAT$$
$$IP(in_{IP}) = 1 \iff SAT(T(in_{IP})) = 1$$
where $in_{IP}$ is an input for the IP problem and $T(in_{IP}) = in_{SAT}$ is a boolean formula (input for the SAT problem).

First, I have considered a particular case for IP, where
$$x_1 +x_2 + \cdots +x_n \leq p$$
$$x_i = 0 \ \text{or} \ x_i = 1, \ \forall i =1..n, \ \forall p \geq0 $$
Translated into boolean language, the transformation will construct a formula where at most p variables must be set to true for the formula to be satisfiable.

Next, I've considered a concrete example, constructing the following ROBDD that allowed me to express the following inequality: $$x_1 + x_2 + x_3 \leq 2$$
$\hskip 2.5in$

where continuous arrow means 1 and dotted arrow means 0. I have also invented the variabiles $x_i\_$ that somehow mirrors the behaviour of $x_i$ sub-component (i.e. swaps routes).

Now, is there a way I can formalize this whole process, that is, express the concept of at most in boolean algebra language? I think this is the key to find the actual transformation.

The existence of such a reduction follows immediately from the Cook-Levin theorem, which guarantees that you can reduce any problem in NP to SAT and describes explicitly one way to do it.  Just work through the steps of the proof of the theorem (which can be found in any textbook) and you'll obtain a valid reduction from 0-1 ILP to SAT.


Does the proof of undecidability of the Halting Problem cheat by reversing results? I have trouble understanding Turing's halting problem.

His proof assumes that there exists a magical machine $H$ which could determine whether a computer would halt or loop forever for a given input. Then we attach another machine that reverses the output and we have a contradiction and therefore $H$ cannot exist.

My concern is that it seems as though we are saying an answer is wrong because we reversed it. As an analogy, if there is a machine called $A$ such that outputs a correct answer on certain inputs and an incorrect answer on others. Then we attach another machine that reverses the result of $A$ so the combination the two machines have a contradiction with how $A$ is defined. The two machines now generate incorrect answers for inputs that $A$ is defined to output correct answers and outputs correct answers for inputs that $A$ is defined to output incorrect answers. Would this be called a contradiction, and therefore there does not exist a machine that outputs correct answer on some inputs and incorrect answers on others?

Short version: The outputs of the machines are not correct or incorrect, they are just contradictory, which proves that the initial machine that decides whether the input machine halts on the given string or not can't exist.

Long version: First we'll sketch the proof (or at least one version of it - there are many).

Assume that we have a Turing Machine $\mathrm{HALT}(\langle M\rangle, x)$ that decides whether the Turing Machine $M$ halts on input $x$ or not.
Using $\mathrm{HALT}$ we construct a machine $\mathrm{FLIP}(\langle M\rangle, x)$ which uses $HALT$ to check whether $M$ halts on $x$ or not, then does the opposite, i.e. if $M$ halts on $x$, $\mathrm{FLIP}$ loops, if $M$ does not halt on $x$, $\mathrm{FLIP}$ halts.
Finally we create a TM $\mathrm{C}(\langle M \rangle)$ (I ran out of good names), which takes the description of a TM and runs $\mathrm{FLIP}$ with input $(\langle M \rangle, \langle M \rangle)$, outputting whatever $\mathrm{FLIP}$ outputs.

It is important to note that as long as the decider $\mathrm{HALT}$ exists, each of these steps is simple to implement; $\mathrm{FLIP}$ just has to use $\mathrm{HALT}$ to check what to do, and $\mathrm{C}$ just duplicates its input to pass to $\mathrm{FLIP}$.

The contradiction arises when we look at what happens when we run $\mathrm{C}(\langle\mathrm{C}\rangle)$. Either $\mathrm{C}$ halts when given itself as input or not. $\mathrm{HALT}$ will decide this:

If $\mathrm{C}$ halts on input $\langle\mathrm{C}\rangle$, $\mathrm{HALT}$ will say $\mathsf{Yes}$, but then $\mathrm{FLIP}$ will loop, so $\mathrm{C}$ will loop, contradicting $\mathrm{HALT}$.
If $\mathrm{C}$ loops on input $\langle\mathrm{C}\rangle$, $\mathrm{HALT}$ will say $\mathsf{No}$, but then $\mathrm{FLIP}$ will halt, so $\mathrm{C}$ will also halt, contradicting $\mathrm{HALT}$.

As each of the steps in the construction is clearly sound, we can only conclude that $\mathrm{HALT}$ can't exist; we have constructed a case where no matter what it says, $\mathrm{HALT}$ can't possible decide what to output, i.e. the problem is undecidable. Just to really hammer on the point a bit, $\mathrm{HALT}$ can't exist - that is there can't be a TM that decides the Halting Problem - because there is at least one case we have explicitly constructed where there is no logically possible answer. Remember a decider is not allowed to output the wrong answer and has to output something, but in the case we have constructed, both possible answers are wrong.


Chaitin's constant is normal? According to this source, Chaitin's constant $\Omega$ is normal.

  Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm to compute its digits. Indeed, each halting probability is Martin-Löf random, meaning there is not even any algorithm which can reliably guess its digits.

Source (Wikipedia)

Furthermore, the definition of normal is that each digit occurs with equal probability $1/b$. And that each duets of digits occur with $1/b^2$ probability and every triplets occurs with probability $1/b^3$ and so on.

Chaitin's omega is calculated via

$\Omega = \sum_{p \in halts} 2^{-|p|}$

Writing $\Omega$ in binary, we obtain a list of 0 and 1. For example,

2^-1=0.1 +
2^-2=0.01 +
2^-3=0.001 +
~skip 2^-4 as it does not halt
2^-5=0.00001 +
...
=\Omega
=0.11101...

Clearly, we can see that the position of each bits corresponds to the halting state of the program of length corresponding to the bit.

Here is what I am struggling with

If $\Omega$ is indeed normal, then it means that exactly 50% of programs halt and exactly 50% do not. This seems very counter intuitive.

For example, suppose I generate java programs by randomly concatenating single characters. The majority of them, I would guess more than 99.99% would not even compile. Would this not imply that at least 99.99% of them will not halt? How do we justify that exactly half will halt and exactly half will not, by virtue of $\Omega$ being normal.

Or is wikipedia incorrect about $\Omega$ being normal?

In contrast to your example, Chaitin's constant is not defined as follows:

$$ \Omega = \sum_{n\colon \text{$n$th program halts}} 2^{-n}. $$

Instead, there is a set $\Pi \subseteq \{0,1\}^*$ of allowed programs which is prefix-free (no string is a prefix of another string). Each of the programs in $\Pi$ is legal (this negates your Java example). If the programs are encoding in unary then it is indeed the case that the $n$th program has length $n$, and then your definition of $\Omega$ works. But for other encodings, the definition of $\Omega$ is

$$ \Omega = \sum_{ p \in \Pi\colon p \text{ halts} } 2^{-|p|}, $$
where $|p|$ is the length of the binary string $p$. Kraft's inequality shows that $\sum_{p \in \Pi} 2^{-|p|} \leq 1$.

Chaitin's constant is algorithmically random: the (prefix) Kolmogorov complexity of the first $n$ bits is $n - O(1)$. To show this, note first that $\Omega_n$, the first $n$ bits of $\Omega$, suffice to determine whether a program of length $n$ (under the encoding $\Pi$) halts or not. Indeed, as a fraction, $\Omega_n \leq \Omega < \Omega_n + 2^{-n}$. Run all programs in parallel, and whenever $p$ stops, add $2^{-|p|}$ to some counter $C$ (initialized at zero). Eventually $C \geq \Omega_n$ (since $C \to \Omega$ from below). At this point, if the input program of length $n$ didn't halt, then you know that it doesn't halt, since otherwise $\Omega \geq C + 2^{-n} \geq \Omega_n + 2^{-n}$.

Given this, suppose that for some $K>0$ and infinitely many $n$, you could compute $\Omega_n$ using $n - K$ bits. For each such $n$, you can find a string whose Kolmogorov complexity is larger than $n$, by considering the output of all halting programs of length at most $n$.  For large enough $K$, the result is a program of length at most $n$ for computing the a string whose Kolmogorov complexity is more than $n$. This contradiction proves that for some $K$, the Kolmogorov complexity of $\Omega_n$ is at least $n-K$.

Algorithmic randomness of $\Omega$ implies, in particular, that the frequency of 0s and 1s in its binary expansion tends to 1/2. Indeed, suppose that for some (rational) $\epsilon > 0$ there exist infinitely many $n$ such that the fraction of 1s in $\Omega_n$ is at most $1/2-\epsilon$. Since there are only at most $2^{h(1/2-\epsilon)n}$ strings with at most $1/2-\epsilon$ many 1s, we can compress $\Omega_n$ to size $h(1/2-\epsilon)n + 2\log n + C_\epsilon$ (the constant $C_\epsilon$ depends on $\epsilon$ since the program needs to know $\epsilon$). However, this is $n - \omega(1)$, contradicting the algorithmic randomness of $\Omega$.


Bellman–Ford negative path meaning In the Bellman–Ford algorithm, what is the practical meaning of
having a negative path between routers?
I have tried searching the net but didn't find any data

thanks
Eli

In the context of network routing, negative-weight edges are meaningless.

Bellman–Ford is just an algorithm for finding lowest-cost paths in a weighted graph. The algorithm itself doesn't know or care what the vertices, edges and weights mean: it just finds paths. Interpreting those paths is for the user.


Showing semidecidability without using diagonalization All the methods I know which shows a given language $L$ is $RE$ but note $REC$ deep down boils down to the cantor's diagonalization arguement in one way or the other, and most commonly it boils down to reducing it to membership/halting problem.
Is there any other fundametnally different way of showing some language is $RE$ but not $REC$, or otherwise is there any heuristic arguement as in we must employ diagaonlization arguement in some form (see also: https://ncatlab.org/nlab/show/Lawvere%27s+fixed+point+theorem)?

Your question is a bit hard to answer, since "diagonalization" is not a formal concept (but see below). For example, does the following argument count as diagonalization? Consider the following function: $f(n)$ is the first string not generated by the first $2^n$ Turing machines. If the halting problem is decidable, then $f(n)$ is computable, and so its Kolmogorov complexity is $O(\log n)$. However, by construction, its Kolmogorov complexity is $\Omega(n)$, and we reach contradiction for large enough $n$.
One thing which is common to this proof and the usual one is the use of proof by contradiction. What happens if we disallow proof by contradiction? Can we prove that the halting problem is undecidable in constructive mathematics? I don't know the answer, but if it is negative, then this explains why proof by contradiction is necessary.
Another relevant piece of information is relativization. The halting problem is undecidable even relative to an oracle. Therefore, there should be an undecidability proof which uses only relativizing techniques. While this does not imply that any proof uses only relativizing techniques, perhaps it means that the "best" proofs should use such techniques. The advantage of this point of view is that it gives a slightly less informal definition of diagonalization, namely, any technique that relativizes.
Finally, let me mention that Kozen formalized the concept of diagonalization in his paper Indexings of subrecursive classes, and showed that every separation of complexity classes (subclasses of computable functions) can be proved by his notion of diagonalization. In his setting (which doesn't include undecidability proofs), diagonalization is the most general type of proof, which can prove all true statements. This means that any proof at all (of such statements) can be cast as a proof by diagonalization.


What does it mean to have a continuous action space w.r.t. to reinforcement learning? Last time I posted this question I got criticised for not being specific enough, hence this is my second attempt at trying to understand what it means to have a continuous action space.

Please refer to this paper, page 5 (A Survey on Policy Search for Robotics
by Marc Peter Deisenroth, Gerhard Neumann and Jan Peters. Foundations and Trends in Robotics. 2013).

The authors say:

  The RL algorithm has to manage (i) high-dimensional continuous state
  and action spaces, (ii) strong real- time requirements, and (iii) the
  high costs of robot interactions with its environment.

I do not understand how an action can be continuous, in the same way that a state-vector is continuous by virtue of having elements that are simply $x_k \in \mathbb{R}^D$ for a state vector $\mathbf{x} := [x_1,\ldots,x_K]^T$. But how can an action be quantified in the same way? It obviously can I simply do not understand how.

When you're driving of your car and you turn the wheel, is that a discrete or a continuous action?  It's continuous, because you can control how much you turn the wheel.  How much do you press the gas pedal?  That's a continuous input.  This leads to a continuous action space: e.g., for each positive real number $x$ in some range, "turn the wheel $x$ degrees to the right" is a possible action.


Is the output of a Mealy/Moore automaton a regular language? How can I prove that the output sequence of Mealy Moore Machine is a Regular Language ?
And what if transition outputs more than one character ? How can we prove for this case that the language in (1) and (2) are same ?

Can I do something like this -

The right side one is Mealy Machine. So can I prove like making a machine in left with transitions using output sequence of Mealy Machine ?

By discarding the input-letters you only consider the output language of the respective Mealy automaton. Effectively you obtain a finite state automaton that recognizes the output language and because it is a finite state automaton, which may be non-deterministic, the language it accepts is regular.

The length of the output of a Mealy-transition is irrelevant as you may have for example$aa\in\Gamma$, where $\Gamma$ denotes the output alphabet of a Mealy automaton.


runtime of problems vs algorithms I know that a solving a specific problem can have different runtimes on different models of computation. But can a specific algorithm have different runtimes on different models of computation?

Also, would an algorithm be considered the high level description or the implementation level description of the procedure you need to do?

Yes it can. When you take RAM model and your algorithm has a lot of multiplications (dominant operation), your multiplications take unit time. Even if the numbers are $2048$ bit numbers. But if you take multitape Turing Machine as your model, the cost of multiplication matters and will be included in complexity.

Algorithm is high level description, implementation will vary. Getting back to multiplication, algorithm describes that in one step you have to multiply two numbers, but if numbers are bigger than computer words instead of writting "*" you have to implement it.


Counting the solutions to a restricted 0-1 knapsack problem Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ :

Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is  represented by a fraction $\frac{p}{q}$ in its lowest terms.

Output:  the number of 0-1 solutions (i.e. those having $s_i\in \{0,1\}$) to $s_1 + s_2 + \dots + s_n \leq s$.

  What is the counting complexity of $\mathsf{\#IDKNAP}$?

Let $k := \lfloor s \rfloor$.  The problem asks for the number of $n$-bit vectors with at most $k$ bits set to $1$. The solution is $\sum \limits_{i=0}^k \binom{n}{i}$, for which there is no closed form in general,
and thus cannot be computed in polynomial time in the input size.

So (I think) $\mathsf{\#IDKNAP}$ would be either $\mathsf{NP~Hard}$ or $\mathsf{\#P~Hard}$. It seems to be insufficiently general to encode arbitrary  $\#\mathsf{KNAPSACK}$ problems, which are $\mathsf{\#P~Hard}$.
On the other hand, $\mathsf{\#IDKNAP}$ has exponentially less input size than general knapsacks, for which the weight vector $(w_1,\ldots,w_n)$ has at least $n$ bits.

There are almost-matching lower and upper bounds for the running time of the best algorithm for this problem, considered as a function of $n$.  In particular, we can prove that the complexity is $\Omega(n)$ and $O(\text{poly}(n))$, when considered only as a function of $n$.

For the upper bound, there's an algorithm whose running time is polynomial in $n$.  Without loss of generality we can take $k \le n$ (for terms where $i>n$ contribute nothing to the sum).  Also you can compute ${n \choose i}$ in time polynomial in $n$.  Therefore, the whole sum can be evaluated in time polynomial in $n$.  In other words, it's solvable in pseudo-polytime.

The size of the output can be as large as $2^n$ (e.g., where $k=n$), so the output can take $\Theta(n)$ bits to represent.  This is exponential in the size of the input.  Thus, any algorithm for the problem must have worst-case running time at least $\Omega(n)$.


Maximum number of configurations of Turing machine after $n$ moves I came across following question:

  What are maximum number of configuration of Turing Machine after $n$ moves?

The answer given was:

  $k^n$, where $k$ is a branching factor.

And that "branching factor" left me confused. So I gave some thoughts: Given $Q$ be total number of states, $\Gamma$ be a tape alphabet and two moves, left and right $\{L,R\}$, for every transition function, we have $2^{Q\times \Gamma \times 2}$ possible transitions at each of those $n$ moves. Thus, $k$ must be $2^{Q\times \Gamma \times 2}$. So, total number of configurations of Turing machine after $n$ moves must be ${(2^{Q\times \Gamma \times 2})}^n$. Am I correct with this?

Note that you are bounding the maximal number of configurations, that the machine can be in, from above. To see it more clearly, when a TM $M$ runs on a finite word $w$ it induces a configuration tree $G = \langle V, E\rangle$ where:

$V$ is the set of configurations that $M$ can be in when it runs on $w$,
$q_0w$ is the initial configuration of $M$ on $w$ and it is the root of the configuration tree,
and the edges in $E$ are defined such that $u$ is a child of $v$ whenever $u$ a consecutive configuration of $v$ (by consecutive we mean that it is possible to reach $u$ from $v$ without violating the transition function of $M$).

As you have mentioned, $k$ is a branching factor, and we usually mean by that the maximal branching degree in the configuration tree. In this aspect you're not correct, $k$ is at most $|{Q\times\Gamma\times \{L, R\}}| = {2|Q|\cdot |\Gamma|}$, and this follows from the definition of the transition function. Indeed, $k$ bounds from above the number of consecutive configurations (which is a subset of configurations) and not the number of all possible subsets of configurations of the TM.

Considering the configuration tree, it is a tree of height ($n = |w|$) with branching degree $k \leq {2|Q|\cdot |\Gamma|}$. Now its not hard to see that such a tree has at most $k^n$ leaves which bounds from above the number of configurations that $M$ can be in when it runs on a word $w$ of length $n$.

A thing worth mentioning is that, $k$ is a constant that does not depend on the input word $w$ (on $n = |w|$) or on a specific configuration tree, and we know that it exists. This sometimes makes life a bit easier as some algorithms/proofs rely on its existence to conclude some upper bounds.


What's the formal definition of Big-O notation for functions of more than one variable? For functions of a single totally ordered variable, I already know that $f(n)$ is $O(g(n))$ if and only if $\exists m. \exists c. \forall n. (n \ge m) \rightarrow [ f(n) \le c \cdot g(n) ]$.

What I don't know is the meaning of $O(g(n_1, n_2 \dots n_k))$ for $k > 1$ totally ordered variables. What's the formal definition?

There are many possible definitions; see e.g. Rutanen et al. [1].

Generally speaking, if you define your $O$ over domain $X$, you will need an order relation $\leq$ on $X$. The definition then reads:

$\qquad O(g) = \{ f : X \to \mathbb{R}_{\geq 0} \mid \exists\,x_0 \in X, c \in \mathbb{R}_{>0}.\ \forall\,x\in X.\\
\qquad\qquad\qquad x_0 \leq x \implies f(x) \leq c \cdot g(x) \}.$

So if $X = \mathbb{N}^k$ you can use lexicographic order, element-wise $\leq$, ...

Beware that the properties your $O$ has depend on both the definition and the the order you choose. The outcome may not be as expected.

A general definition of the O-notation for algorithm analysis by K. Rutanen et al. (2015)


Will encoding affect computability? I think this question arises from not having a clear idea on encoding. So, If I have a problem intuitively there may be many ways of encoding it using TM's alphabet set. Slight variation in the encoding may(intuitively) not affect the computability of the problem, Is it true? Can I have a computable problem which on changing the encoding turns uncomputable?For eg given a graph and two vertices, the problem is whether there is path between them. We know this is compuatable. But if we consider encoding as just a mapping, then If I have encoding such that set of all instance of the problem with the answer as yes mapped to some undecidable language(bijectively)?Is it possible?

As long as there's a computable mapping between the two encodings, changing from one to the other won't affect computability, since computable functions compose. If there isn't a computable mapping between the encodings, you can't effectively use at least one of them, since there's no way to figure out what the encoding of your input should be in that scheme. (For example, suppose you come up with a coding of graphs that isn't computably translatable from the adjacency matrix. How would you use that encoding? If I give you a graph, you can't figure out what string encodes it.)


Unique 3SAT to Unique 1-in-3SAT Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment.

It was made from a binary multiplication circuit where I multiplied two primes numbers A and B such that A*B=S where S is a semiprime number. I added the conditions that A != 1, B != 1 and A <= B, then added the value of S to the formula make sure the assignment is unique. The only way to satisfy the formula is to put the values of primes A and B in correct order in the input bits.

In 1-in-3SAT, we force that exactly 1 literal should be true in each triplet and two others false. If exactly 2 literals are true we can flip all the iterals in the clause to get an equivalent 1-in-3SAT clause (in other words 2-in-3SAT is the same problem).

Basic observation: While a regular OR clause eliminates 1 possibility out of 8, a 1-in-3 clause eliminates 5 possibilities out of 8.

3SAT can be reduced to 1-in-3 SAT, such that if the 3SAT formula is satisfiable then so is the reduced formula.

However, reductions do not seem to preserve the number of assignments, by introducing new variables without forcing their value.

Can Unique 3SAT be reduced to Unique 1-in-3SAT...

Without knowing the correct assignment?
If not, while knowing the correct assignment?

Yes, a 3-SAT formula $\phi$ can be transformed into a 1-in-3 SAT formula $\phi'$ while preserving the number of satisfying assignments.  To avoid ambiguities I will use "$\vee$" between literals of a 3-SAT clause, and commas between literals of a 1-in-3 SAT clause.

Let me preliminarily show that, given two literals $a$ and $b$, we can simulate a new type of clause $(x = a \wedge b)$ that forces the value of a new variable $x$ to be $a \wedge b$ using only 1-in-3 SAT constraints, without introducing any new solution.

Consider the cluases:
$$
(\overline{b}, c, x) \wedge
(a, c, d) \wedge
(\overline{a}, e, x) \wedge
(b, e, f)
$$

If $a=\top$, and $b=\top$, then the 2nd and 4th clauses ensures that $c=d=e=f=\bot$. The 1st and 3rd clauses then ensures that $x=\top$.

If $a=\top$, and $b=\bot$, then the 2nd clause ensures that $c=d=\bot$. The 1st clause then ensures that $x=\bot$.
The 3rd clause ensures that $e=\top$, and the 4th clause implies $f=\bot$.

The case $a=\bot$, and $b=\top$ is symmetric.

If $a=\bot$ and $b=\bot$, then the 1st and 3rd clauses imply $c=e=x=\bot$.
The 2nd and 4th clauses ensure $d=f=\top$.

I am now ready to transform a formula $\phi$ of 3SAT to a formula $\phi'$ of 1-in-3 SAT.
Consider now a clause $(a \vee b \vee c)$ of $\phi$. This can be transformed into the following equivalent 1-in-3 SAT clauses:

Add a new variable $x$ that is true iff $a$ is false and $b$ is true. This is encoded by the clause $(x = \overline{a} \wedge b)$.
Add a new variable $y$ that is true iff $a$ is false, $b$ is false, and $c$ is true. We will need an additional variable $z$. The clause $(z = \overline{a} \wedge \overline{b})$ ensures that $z$ is true if and only if $a$ is false and $b$ is false. Then, the value of $y$ can be enforced by the clause $(y = z \wedge c)$.
If $(a \vee b \vee c)$ is true then at least one of $a$, $b$, or $c$ is true. This means that exactly one of $a$, $x$, and $y$ is true. On the converse, if  $(a \vee b \vee c)$ is false, then at all of $a$, $x$, and $y$ are false. This shows that $(a \vee b \vee c)$  is satisfiable if and only if $(a, x, y$) is satisfiable.

We have then constructed an equivalent 1-in-3 SAT formula $\phi'$ that uses a superset of the variables of the original 3 SAT formula $\phi$.
A truth assignment to the variables of $\phi'$ satisfies $\phi'$ if and only if the assignment restricted to the variables of $\phi$ satisfies $\phi$.
Therefore, if any new solution to $\phi'$ is introduced, it must be because of the newly added variables $x$, $y$, and $z$ (one set for each clause). However, the values of these variables are completely determined by the values of the variables of $\phi$.


How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL? I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help.

The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should choose which symbols to mark.

I tried with all the first $N$ $a$s (and also other combinations), but then for $v=a^j$ and $x=a^j$ (and $w=b^{N+1}$) pumping doesn't get a string out of $L$.
My idea is that I should involve both $a$s and $b$s between the marked symbols and somehow force the pumping for both, but I don't know how.

Let $N$ be the constant of the Pumping Lemma for CFL.

Let be $z=a^N b^{N+1} a^N b^{N+1}$.

let's analyze some of the possible decompositions of $z$ in $uvwxy$:

(note that $vx$ has always at least one symbol)

$u=\epsilon$, $v=a^*$, $w=a^*$, $x=a^*$, $y=b^{N+1} a^N b^{N+1}$.
just pumping once we get a string out of $L$.
$u=a^*$, $v=a^*$, $w=a^*$, $x=a^*$, $y=b^{N+1} a^N b^{N+1}$. same as above.
$u=a^*$, $v=a^*$, $w=a^*$, $x=a^*b^*$, $y=b^* a^N b^{N+1}$. same.
$u=a^*$, $v=a^*$, $w=a^*$, $x=b^*$, $y=b^* a^N b^{N+1}$. same.
$u=a^*$, $v=a^*$, $w=a^*b^*$, $x=b^*a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
$u=a^*$, $v=a^*$, $w=a^*b^{N+1}$, $x=a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
$u=a^*$, $v=a^*$, $w=b^{N+1}$, $x=a^*$, $y=a^* b^{N+1}$. it can't happen because $\mid vwx \mid$ would be $>N$.
$...$

Anyway the problematic case is 7. because it could be $u=a^k$, $v=a^j$, $w=b^{N+1}$, $x=a^j$, $y=a^kb^{N+1}$ with $k+j=N$, so that pumping doesn't push $z$ out of $L$. But again, it can't happen otherwise we would have $\mid vwx\mid >N$, which is not possible and it is guaranteed by the lemma.


Unable to understand control flow in KMP algorithm I am facing problem in understanding the KMP algorithm as given in the book  "Introduction to Algorithm" by Cormen et. al. (Chapter 32):

With respect to the above algorithm, I have following question:

In both the algorithms, where exactly (which line number?) while loops, if and for loop ends? It is difficult to visualize the functioning of the algorithm without knowing the 'end' for each loop and conditional statements.
On line number 6 in KMP-MATCHER() and COMPUTE-PREFIX-FUNCTION(), what is the need of checking q>0 and k>0, when we know q and k will always be 0 or positive. Or do the authors want to test q!=0, k!=0?
If q=0 and i=1 in KMP-MATCHER(), from 6 to 10 which line will be executed (If I get answer to 1- above then I can find this)

As explained in the comments, indentation marks code blocks. It is a standard way to denote them. while of line 6, repeats line 7, but has nothing to do with the if on line 8.
Indeed it only matters whether q and k are not zero.


How can I find a number whose sum of digits' cube is equal to n I'm given a number $n$ and I have to find the smallest number possible whose sum of digits' cube is equal to $n$. For example $n=9$ then output should be $12$, because $1^3 + 2^3=9$.

Let us consider the more general problem in which we fix integers $0 < a_1 < \cdots < a_m$, and then given a positive integer $n$, we want to determine the smallest non-negative integer combination $\sum_{i=1}^m d_i a_i$ which is equal to $n$, if any exists, or determine the none exists. Here one combination $(d_1,\ldots,d_m)$ is smaller than another $(e_1,\ldots,e_m)$ if either $d_1+\cdots+d_m < e_1+\cdots+e_m$, or $d_1+\cdots+d_m = e_1+\cdots+e_m$ and for some $i$ we have $d_1=e_1,\ldots,d_{i-1}=e_{i-1}$ and $d_i > e_i$.

The main observation is that any optimal solution satisfies $d_i < a_m$ for all $i < m$. Indeed, if $d_i \geq a_m$ then we can decrease $d_i$ by $a_m$ and increase $d_m$ by $a_i$ to obtain a better solution. (In fact, this shows that $d_i < \mathrm{lcm}(a_i,a_m)/a_i$.) This suggests the following algorithm:

  Go over all possible values of $d_1,\ldots,d_{m-1}$ such that $0 \leq d_1,\ldots,d_{m-1} < a_m$. For each such setting, check whether it can be completed to a solution, that is, whether $a_m$ divides $n-\sum_{i=1}^{m-1} d_i a_i$. Choose the smallest solution, if any exists.

This algorithm runs in time $O(\log n)$, where the hidden constant depends in some horrible way on $a_1,\ldots,a_m$. This is optimal (up to the value of the hidden constant) since clearly we need to read the entire input.

The algorithm above doesn't really help you solve your case in practice, since the hidden constant is too large. Presumably you were supposed to use dynamic programming, an algorithm which runs in time $O(n)$ and finds the minimal length of a solution (perhaps it can also be tweaked to find a solution of minimal value).


How is the run time calculated in this insertion sort algorithm? I am looking at this algorithm in CLRS page 26:

I am a novice when it comes to these things so please make your explanations as simple as possible.
For the cost column, does c1, c2, c4, etc denote a value the same way n does, or are they just labels? My understanding is an operation takes one time unit (such as j=2 is an operation that writes something once, therefore its one time unit) so does c1 mean one time unit?
Secondly, why does key=A[j] happen n-1 times?
Thirdly, line 3 is a comment therefore does not have an execution, so why does it happen n-1 times?

Let me answer step by step:

$c_1, c_2, c_4$ etc. are costs of the operation in the corresponding line. For example $c_1$ is the cost of for: one pass of this line costs $c_1$.
$key=A[j]$ happens $n-1$ times, because we start from $2$ and $n=A.\text{length}$.
As it is commented, its cost is $0$.


What is the time complexity of the following program? Please help me calculate the time complexity of the following program.

int fun (int n) {
  if (n <= 2)
   return 1;
  else
   return fun(sqrt(n)) + n;
}

Please explain.

There were four choices given.

$\Theta(n^2)$
$\Theta(n \log n)$
$\Theta(\log n)$
$\Theta(\log \log n)$

The running time of the function on an input $n$ can be expressed as: $$T(n) = T(\sqrt n) + \mathcal{O}(1)$$

which implies the running time of the function and the number of recursions differ only by a constant.

The recursive chain ends when $n$ has been reduced to some value $k$, where $k \le 2$. The number of recursions, $r$, can be expressed as: $$k^{2^r} = n \implies r = \log_2 \log_k n$$

It follows that the running time is then:

$$\Theta(\log_2 \log_k n) = \Theta(\log \log n)$$


sock matching algorithm There are $n$ pairs of socks, all different. They all went out of the dryer, so there are now $2n$ socks scattered around. Given two socks, the only operation I can do is to decide whether they are identical (- belong to the same pair) or different (- belong to different pairs). What is the best way to sort the socks in matching pairs?

The obvious algorithm is: grab a sock, scan the pile for its matching sock, and put that pair aside. This algorithm requires time $O(n^2)$.

I Found a related question, On the complexity of sock-matching from about 10 years ago, which also describes an $O(n^2)$ algorithm.

If each sock has a numeric ID, or another ordinal property, such as: wavelength of color, then the entire set of socks can be sorted by that ordinal property in time $O(n log n)$, and then the pairs can just be collected with an $O(n)$ scan. But, in this question I assume that there is no order on the socks - we can only tell whether two socks are identical or different.

In a similar question in StackOverflow (How to pair socks from a pile efficiently?), the accepted answer suggests to use a hash, but again, this assumes that each sock can be represented by a set of properties such as color, pattern, etc., so that each property can be handled separately. In this question I assume that the properties of the socks are only accessible via a function that tells whether two socks are identical or different.

There is a paper named Sock sorting, which initially seems related, but actually it deals with another problem, where two socks might seem identical although they are different (this probably makes the problem more difficult).

So, my question is: assuming we only have a binary "identical/different" relation on the socks, can we match the socks faster than $O(n^2)$?

A comparison with a result "different" doesn't add information regarding any other sock in the pile (If sock B didn't match A, and Sock C didn't match A, the chance of B and C  to be a match is still the same as with any other sock). therefor no sorting or organization can be made, rather then knowing for each sock which socks don't match it based on this comparison. this leads back to the naive algorithm, which is $O(n^2)$.

Pretty disappointing...


Complement of Mealy machine How could one reasonably define and construct the complement of a deterministic Mealy machine?

My intuition is that the complement should give exactly the opposite of output strings after a specific input string. I think this means the complement is non-deterministic. So let's define a (non-deterministic) Mealy machine: $\mathcal{M} = \langle S,I,\Sigma,\Omega,\delta,\lambda\rangle$, where

$S$ is a finite nonempty set of states,
$I \subseteq S$ is the nonempty set of initial states,
$\Sigma$ is a finite input alphabet,
$\Omega$ is a finite output alphabet,
$\delta: S \times \Sigma \to 2^S$ is the transition function, and
$\lambda: S \times \Sigma \to 2^\Omega$ is the output function.

A Mealy machine is deterministic iff $\vert I\vert = 1 \land \forall s \in S, \forall i \in \Sigma: \vert\delta(s, i)\vert \leq 1 \land \vert\lambda(s, i)\vert \leq 1$.

I believe defining and constructing the complement is easier if we assume the transition function, and output function are total. That is fine for me.

So, given a Mealy machine $\mathcal{M}$ how would one define, and construct (using an algorithm) the complement $\overline{\mathcal{M}}$?

If the algorithm follows trivially from the definition of $\overline{\mathcal{M}}$ that is fine too.

My first idea is that one could, for every transition, add new transitions (from, and to the same state) that give exactly the complement of outputs. However, I am afraid I am missing important corner cases.

You are right: it is easy to miss corner cases, so whatever you choose to define, you will need to prove that you defined the right thing.

To do so, you need to first define what you actually want, i.e., the language of $\overline{M}$.

From what I can tell, you want
$$\mathcal{L}(\overline M) = \{ (w^I_0 ,w^O_0) (w^I_1 ,w^O_1) \ldots \in (\Sigma \times \Omega)^\omega \mid (w^I_0,w^O_0) (w^I_1 ,w^O_1) \ldots \not\in \mathcal{L}(M)\}$$

If you just just invert the set of possible outputs along an edge, then get an automaton $\overline M$ for which you can then try to prove that it has the right language, i.e., that (1) every word accepted by the automaton is in the language that we defined for it, and (2) vice versa.

Because this seems to be connected to your research, I will not give you the answer whether such a proof works (as I don't want you to force to give non-citation credit to the work of others, which you would need to do if someone else gives you a solution), but rather let you try this out on your own.

Should this approach not work, here is an idea that allows you to cover all corner cases:

Translate the Mealy automaton to a DFA (deterministic automaton over finite words) that
accepts all prefix traces of the Mealy automaton's language
Complement the DFA
Conjunct the DFA with with a DFA accepting all words from $(\Sigma \times \Omega)^*$.
The resulting automaton accepts the words that you want your Mealy automaton to have. So define a suitable translation to a non-deterministic Mealy automaton.

The idea here is the complementation part is done by a well-known and known-to-work algorithm, so you avoid parts of your problem. The last step is still non-trivial, but probably easier than before.


Is every program is equivalent to a Push Down Automata? so I was reading about stack-organized computer. Does a stack-organized computer implies that every program is equivalent to (and not more powerful than) a  Push Down Automata?

No. The class of languages recognised by pushdown automata is the class of context-free languages, whereas the class of languages recognised by Turing machines is the class of Turing-recognizable (aka recursively enumerable) languages. All context-free languages are recognisable but the converse does not hold.


Understanding On-policy First Visit Monte Carlo Control algorithm I am going through the Monte Carlo methods, and it's going fine until now. However, I am actually studying the On-Policy First Visit Monte Carlo control for epsilon soft policies, which allows us to estimate the optimal policy in Reinforcement Learning.

I am having troubles understanding the step in blue of the algorithm. Is the pair St, At NEVER supposed to appears in the given set of states ? In this case, the following pseudo-code will never get realized ? What is the specific case where St, At appears in the set of Action-States ?

Please feel free to ask more details if my question isn't clear enough.

The algorithm is taken from the reinforcement learning book written by R.Sutton and A. Barto.

The highlighted line basically says that time $t$ must be the first occurrence of the pair $(S_t, A_t)$ in the complete trajectory from $0$ up to and including $t$. This is why there is "first-visit" in the name of the algorithm; it only runs updates for $(S_t, A_t)$ pairs if $t$ is the first occurrence (first "visit") of a particular state-action pair in a trajectory.

This condition:

Is always trivially satisfied for the pair $(S_0, A_0)$ (it's the beginning of the trajectory, so we can't possible have observed that state-action pair before)
Is satisfied at time $t = 1$ if and only if $(S_1, A_1) \neq (S_0, A_0)$ (so at least one of the state or the action must be different from the preceding ones)
Is satisfied at time $t = 2$ if and only if $(S_2, A_2) \neq (S_1, A_1)$ AND $(S_2, A_2) \neq (S_0, A_0)$.
etc.


Why is PH in PSPACE? $PH \subseteq PSPACE$.

In order to prove it, one has to show that for a language $A \in \Sigma_k$ (for some $k \in \mathbb{N}$) there exists a turing machine $M_A$ that decides it in polynomial space.

I am having a hard time understanding why this is true. I'll try to explain:

Let's take for example $L \in\Sigma_2$: by definition, $x \in L \Longleftrightarrow \exists y_1\forall y_2 : V(y_1,y_2)=1$. But finding such $y_1$ and checking it against all possible $y_2$s has to take more than polynomial space! The machine has to remember each $y_2$ that it tried in order to make sure that it indeed tried out all of the options, and the number of possible $y_2$s is exponential, which makes it exponential space.

No, it is not necessary to remember all $y$'s tried before. In order to remember that I've tried the numbers $1,2,\ldots,200$, I do not need to remember $3,4,5,6,\ldots,199$. If you try them in order, just remembering the last one is enough.


Fastest algorithm to decide whether a (always halting) TM accepts a general string Given a TM $M$ that halts on all inputs, and a general string $w$, consider the most trivial algorithm (Call it $A$) to decide whether $M$ accepts $w$:

$A$ simply simulates $M$ on $w$ and answer what $M$ answers.

The question here is, can this be proven to be the fastest algorithm to do the job?

(I mean, it's quite clear there could not be a faster one. Or could it?)

And more formally and clear:

Is there an algorithm $A'$, that for every input $\langle M,w\rangle$ satisfies:

If $M$ is a TM that halts on all inputs, $A'$ will return what $M$ returns with input $w$.
$A'$ is faster than $A$.

Dkaeae brought up a very useful trick in the comments: the Linear Speedup Theorem. Effectively, it says:

  For any positive $k$, there's a mechanical transformation you can do to any Turing machine, which makes it run $k$ times faster.

(There's a bit more to it than that, but that's not really relevant here. Wikipedia has more details.)

So I propose the following family of algorithms (with hyperparameter $k$):

def decide(M, w):
    use the Linear Speedup Theorem to turn M into M', which is k times faster
    run M' on w and return the result

You can make this as fast as you want by increasing $k$: there's theoretically no limit on this. No matter how fast it runs, you can always make it faster by just making $k$ bigger.

This is why time complexity is always given in asymptotic terms (big-O and all that): constant factors are extremely easy to add and remove, so they don't really tell us anything useful about the algorithm itself. If you have an algorithm that runs in $n^5+C$ time, I can turn that into $\frac{1}{1,000,000} n^5+C$, but it'll still end up slower than $1,000,000n+C$ for large enough $n$.

P.S. You might be wondering, "what's the catch?" The answer is, the Linear Speedup construction makes a machine with more states and a more convoluted instruction set. But that doesn't matter when you're talking about time complexity.


Formulating a linear program s.t. only extreme point solutions are found If there are many solutions to a linear program s.t. the objective function is minimized/maximized (= optimal solutions are on an edge of the polytope), how can I force an LP solver to find only an extreme point solution?

Perturb the vector of the objective function slightly. If you got multiple optimal solutions than this vector is orthogonal to a facet $F$ of the polytope that defines the feasible area of the LP. Notice that $F$ could be an edge, but also a higher dimensional flat. By changing the objective function slightly you will get an extreme point that lies on the boundary of $F$.

You might want to check that the perturbation was small enough. So check the computed point with the original objective function, if it produces the optimum.


Prove that checking if context free grammar generates word with all symbols is NP-complete - unclear statement about encoing probem in exercise Prove that following problem is complete in NP in sense of Karp.
Given: context free grammar $G$
Check if $G$ generates word containing
all symbols from alphabet
Remark
Above problem should be encoded as langauge over finite alphabet,  although alphabet of $G$ can be arbitrarily big. You can assume that symbols of this alphabet are encoded as binary strings.

My main problem at this moment is that I don't understand Remark.  For me, it should be attached also alphabet of grammar.  Can you explain me in human language what this Remark try to say ?
To be more clear I can say that in other task with the same question, but with given regex and alphabet of regex I did deal with it. However, in mentioned task there was no this awkward Remark.

What the remark is trying to tell you, I think, is that the alphabet of each different grammar $G$ can grow and is not fixed.

For instance. say that you have a language $L$ that you want to reduce to your language, let´s call it $L'$, then, you are allowed to make the alphabet of the different context free grammars inside $L'$ grow as the instances inside $L$ grow. For a bigger instance a bigger alphabet


Do fully optimizing compilers for terminating programs exist? In Andrew W. Appel's book, Modern Compiler Implementation in ML, he says under chapter 17 that Computability theory shows that it will always be possible to invent new optimizing transformations and proceeds to prove that a fully optimizing compiler will solve the halting problem: A program Q that produces no output and never halts can easily be replaced by its optimal representation, Opt(Q), being "L: goto L". So a fully optimizing compiler can solve the halting problem.

So my question is this: Does a fully optimizing compiler exist for terminating programs? My only thoughts are the following: Even though a program is guaranteed to terminate, it can still be arbitrarily complex, and for any concrete optimizing compiler, C, one could perhaps construct a program that takes C as input and somehow produces a worse program as some kind of corner case.

Also, What are the implications of restricting ourselves to terminating programs?

I assume you are interested in optimisation of runtime. As I've written in my comment, that does not sufficiently specify the goal: does an optimisation reduce runtime on any input, every input, all worst-case inputs or even on average?

I will show that all of them are impossible. The proof extends to optimising the length of the program.

Recall that the following problem is not computable:

  Given a context-free grammar $G$ with terminal alphabet $\Sigma$, decide whether
  $\mathcal{L}(G) = \Sigma^*$.

Note furthermore that given a context-free grammar $G$, we can hardcode, say, the CYK algorithm for that one grammar; denote this algorithm by $\mathrm{CYK}_G$. We observe that $\mathrm{CYK}_G$ terminates for all inputs (from $\Sigma^*$).

Now assume that there is an optimiser $\operatorname{Opt}$ which, given an always terminating algorithm $A$, outputs a result-equivalent algorithm which is optimal with respect to runtime. Clearly,

$\qquad \operatorname{Opt}(\mathrm{CYK}_G) = \text{'}\mathtt{return\ true;}\text{'}
        \iff \mathcal{L}(G) = \Sigma^*$

and we have thus constructed a decider for an uncomputable problem, contradicting the assumption.


Upper bound for #Monotone k-SAT (I've recently started studying satisfiability problems. I've tried to be as clear as possible, but I'm not sure if all of the terminology used is correct.)

Consider a collection of $n$ Boolean variables, $x_1,\ldots,x_n$ and a function $F$ on this collection of variables, $F(x_1,\ldots,x_n)$. An assignment of true and false values to each Boolean variable is called a satisfying assignment if $F(x_1,\ldots,x_n)$ is true.

I'm interested in functions $F$ that take the form $(x_{i_1}\vee x_{j_1} \vee \cdots \vee x_{k_1})\wedge \cdots \wedge (x_{i_m}\vee x_{j_m} \vee \cdots \vee x_{k_m})$ where indices are allowed to repeat, a so-called Monotone k-SAT function. Perhaps something worth noting is that not all of the clauses contain $k$ variables, but it is known that $k$ is the most number of variables in all clauses.

Question: What sort of bounds on the number of satisfying assignments for $F$ are known? The worst bound is $2^n$; I'm hoping there is something better.

(Note: this builds on an original question graciously answered by Yuval Filmus here: Number of states in an AND-OR DAG)

A $k$-SAT instance over $n$ variables, monotone or otherwise, has at most $2^n - 2^{n-k}$ solutions.  This is simply the number of possible settings of the $n$ variables minus the least number of settings a single $k$-CNF clause can exclude, assuming all the variables in the clause are distinct.  You only have to consider the case of a formula with a single clause because adding more clauses can never increase the number of satisfying assignments.


Are there programs that never halt and have no non-termination proof? Like black holes in computer science. We can only know they exist but when we have one of them we will never know it's one of them.

There are indeed programs like this. To prove this, let's suppose to the contrary that for every machine that doesn't halt, there is a proof it doesn't halt.

These proofs are strings of finite length, so we can enumerate all proofs of length less than $s$ for some integer $s$.

We can then use this to solve the halting problem as follows:
Given a Turing Machine $M$ and an input $x$, we use the following algorithm:

s := 0
while (True)
    test if machine M halts on input x in s steps
    look at all proofs of length s and see if they prove M doesn't halt on input x
    set s := s + 1

If $M$ halts on input $x$, then it halts in some finite number of steps $s$, so our algorithm terminates.

If $M$ doesn't halt on input $x$, then by our assumption, there's some proof length $s$ where there's a proof that $M$ doesn't halt. So in this case, our algorithm always terminates.

Thus, we have an algorithm deciding the Halting problem which always terminates. But we know this cannot exist, so our assumption that there's always a proof of non-halting must be false.


Decidable? If a Turing Machine M, on input w, will M ever move its read/write head to the left? If a Turing Machine M, on input w, will M ever move its read/write head to the left?
Determine if this violates Rice's Theorem.

1.
I think the answer for Q1 is decidable because we can make a Turing Machine that decides the problem as follows:

Step 1: If M halts on w and it never moved left, reject it.
Step 2: If M ever moves left, halt and accept.
Step 3: If M loops forever (some configuration repeats) then reject it
Step 4: Otherwise, reject (M moves right, eventually encounters a
blank symbol, and moves right forever, which means that M will never
move left. So, reject it.)

2.
We proved that for some language L L(M) is decidable. So, we can say that L(M) is Turing-recognizable. The property 'L(M) is Turing-recognizable' is trivial because there does not exist a Turing-recognizable L2 such that L2 does not belong to L. Thus, our problem is decidable with the following decider:

"Step 2: If M ever moves left, halt and accept."

, and this does not violate Rice's Theorem.

I'm afraid that your logic doesn't make sense, since you can't implement Step 1. In order to implement it, you'll have to run $M$ and see if it every halts, but this is impossible, since it's the halting problem.
Nevertheless, the problem is decidable. The details of this argument depend on the exact Turing machine model, but in order to illustrate the basic idea, it suffices to consider the simplest possible model, in which there is only one head, and at each step, it has to move (either one step to the left, or one step to the right). We simulate $M$ for $|w|$ steps. Either it has moved to the left (in which case we know the answer), or otherwise, it has gone past the input.
In the latter case, suppose that the Turing machine is at some state $q$ after $|w|$ steps. Let's say that a state is bad if when $M$ reaches it, if the input under the head is blank, then it moves left. Construct a directed graph in which there is an arrow from $q$ to $p$ if $M$ transitions from $q$ to $p$ when the input under the head is blank. There are three cases:

The path starting at $q$ reaches a bad state. In this case the head of $M$ will eventually move left.
The path starting at $q$ reaches a halting state or closes a cycle, in both cases not going through a bad state. In this case the head of $M$ will never move left.

This shows how to decide whether $M$ every moves left upon reading $w$.

This might seem to contradict Rice's theorem, but it doesn't. The reason is not what you state — the problem is not trivial: there are pairs $(M,w)$ for which $M$ does move left when running on $w$, and there are other pairs when this doesn't happen. Rather, the property of never moving left is a syntactic property rather than a semantic property: it depends on the Turing machine $M$ instead of on its language $L(M)$.


For what kinds of languages is min |NFA| = Ω(min |DFA|)? Consider a regular language $L$. Let $D(L)$ be a minimal DFA for $L$ and $N(L)$ be a minimal NFA for $L$ (minimal in the sense of the smallest possible number of states for an automaton that recognizes the given language). Write $|A|$ for the size (number of states) of the automaton $A$. In general, $|N(L)|$ can be a lot smaller than $|D(L)|$ (down to $\lg |D(L)|$, since determinization is exponential in the worst case).

I am interested in languages for which the minimal NFA is guaranteed to be at least a fraction of the size of the DFA: $|N(L)| \ge k |D(L)|$. What families of regular languages have this property? In other words, for what family of languages $(L_n)$ such that $|D(L_n)| = n$ is $|N(L_n)| = \Omega(n)$?

Perhaps this is too trivial to bear mentioning, but I'll mention it anyway: one class of languages comes to mind (although there may be much more interesting classes of languages than this which satisfy the property).

Consider a family of languages $\{\{\epsilon\}, \{w\}, \{ww\}, ..., \{w^n\}, ...\}$ where $w \in \Sigma^*$. A minimal NFA for the $n$th language will have $n|w|+1$ states (assuming no dead state), whereas a minimal DFA will have $n|w|+2$ states (assuming a single dead state). We have that $n|w|+1 = \Omega(n|w|+2)$.

We get another family by allowing each language to accept up to $n|w|$; this is the family $\{\{\epsilon, w, ww, ..., w^n\} \mid n \geq 0\}$. The automata for these languages are practically identical to the corresponding automata from the other family, except these have more accepting states.

These happen to be families of finite languages. We could, of course, get a family of infinite languages as follows: $\{\{w^nw^*\} \mid n \geq 0\}$.

Consider any family of languages which consist of a single word. For any such language, the ratio of $|\min DFA|$ to $|\min NFA|$ will be less than $2$, so such a family of languages must satisfy the property. Since there are countably many finite strings over any alphabet, and since we're considering any possible subset thereof, we get an uncountable number of language families in this manner.

FWIW, to get these examples, my thinking was that we're looking for languages that involve doing something which an NFA can't do much better than a DFA. Accepting some random string, and nothing else, is notable in this regard. I guess more generally, there's an informal notion of "straightforwardness of the DFA" that seems to be related to what's being asked.

You know, come to think of it, I think we can generalize this a bit more: any family of languages with the following form should work: $L_n = \{s_0s_1...s_i\}L$ for $n \geq 0$, where $L$ is any regular language and $s_n$ is any finite string. Suppose for $L$ that $|\min DFA| = x$ and $|\min NFA| = y$. Then the family $L_n$ should always have $|\min DFA| / |\min NFA| \leq x/y$.

I don't know whether this is pertinent, interesting or useful, but I thought if nothing else this might revive the question.


How do I assign homes to hospitals based on locality? (clustering, kmeans?) I have a large set of $(X)$ hospitals and $(Y)$ homes, where $(Y)$ is much larger than $(X)$, and their respective coordinates. Each hospital can handle any home within a 50 mile radius, and up to 10,000 homes. Homes can be assigned to one hospital. How do I create assignments of homes to hospitals such that as many homes can be assigned a hospital? Performance doesn't matter that much.
I was thinking of potentially getting each hospital to do a breadth first search to reach as many homes as possible near it. For this, I was thinking of calculating the distance to all homes from each hospital, then going through each home and matching with the nearest hospital until all homes are filled or can't be any more.
Would this be a good approach? What would a better approach be? Are there clustering algorithms that could help here such as kmeans?

Construct a graph $G=(V,E)$ where $V$ contains two nodes $s$ and $t$, a node $u_x$ for each hospital $x \in X$, and a node $v_y$ for each home $y \in Y$.
There is an edge between $s$ and each $v_y$ of capacity 1.
There is an edge of capacity $10000$ between each $u_x$ and $t$.
Moreover, there is an edge $(v_y, u_x)$ if an only if $y$ is within $50$ miles from $x$. Edges $(v_y, u_x)$ have unbounded capacity.
Compute a maximum flow $f$ from $s$ to $t$. The value $|f|$ of the flow tells you the maximum number of homes that can be assigned to some hospital. Moreover, $f$ itself tells you a possible assignment: assign $y \in Y$ to $x \in X$ if and only if $f(v_y, u_x)=1$.


NFA automata with ϵ moves proof let's say L is a regular language.
And there in an NFA automata with epsilon moves A,in which for every accepting state δ(q,σ)=Ø.
How can I prove that there must be an automata A as defined for L?

I will give you some intuition how to build such NFA.

Because L is a regular language, then we can find deterministic finite automata F which accepts this language. Based on that we will build our NFA. Let's add epsilon transitions from all F's accepting states to new state which will be the only accepting state in our NFA. You can now prove, that such automata will accept L.


When the data size and processor speed are both multiplied by 10, then a linearithmic algorithm takes double the time to finish? Robert Sedgewick mentioned, if a computer can handle 10x data and the processor is also 10x as fast, then a $ O(n^2) $ algorithm actually runs slower than before.

Is this the correct idea when a computer has 10x RAM and can handle 10x data all at once, and also have a processor that is 10x faster, then:

A $ O(n^2) $ solution is slower, because now $ n^2 $ is 100 times, but processor is only faster by 10 times. So the time it takes to solve the problem is 10 times more. So if it took 1 hour to solve the problem before, now it would take 10 hours.
If it is a $ O(n \log n) $ solution, then roughly speaking, for $ n \log n $, it is

$ (100 \log 100) / (10 \log 10)
  = (100 / 10) \times  (\log 100 / \log 10)
  = 10 \times log_{10} 100 = 20 $

and since the processor is 10 times as fast, that means now the algorithm is "half as fast"? (meaning if it took 1 hour to solve the whole problem before, now it would take 2 hours)

I don't like how you expressed this - the ten times faster computer is ten times faster. It will solve the same problem and answer the same question ten times faster. Of course if you give it a question that would take 100 times longer on the old computer, then it will take only 10 times longer on the new computer.

If you had an algorithm that took n log n microseconds (and in CS "log" usually means log base 2) to solve a problem of size n, a problem of size 10 n would take 10n log (10n) microseconds on the old computer, and n log(10n) microseconds on the new computer.

log (10n) isn't ten times or twice as much as log n - the factor 10 turns into a constant. log (10n) = log n + log 10 ≈ log n + 3.3. If n = 10 it's twice as much. If n = 10 billion it's only ten percent more.

Two things to consider: No computer is just "ten times faster". A computer does many different kinds of operations. Some may be ten times faster, some even more, some less. And Big-O is concerned about asymptotic values: I could have an algorithm that takes on my computer n^2 microseconds if n ≤ 1,000,000 and 10n^2 microseconds if n > 1,000,000. So if you want to find actual execution times, you need more than Big-O.

And it is very common that actual execution times are quite different from what Big-O makes you belief when n is small. For example, let f(n) = n + 1000 log n. f(n) = O(n). But for n ≤ 10,000 f doesn't behave very linear at all.


Vertex Cover of size k in a tree? What is a polynomial time algorithm for finding a vertex cover of size $k$ in a tree? Would depth first or breadth first search be efficient or is there some other algorithm that finds the vertex cover that takes $n^k$ time rather $2^n$ time?

Hint: Suppose $x$ is a leaf and $y$ is the unique neighbor of $x$. Show that there is always a minimum vertex cover which contains $y$. (Every vertex cover contains either $x$ or $y$; if it contains $x$, then replacing $x$ with $y$ we still get a vertex cover.)


Big-O proof for a recurrence relation? This question is fairly specific in the manner of steps taken to solve the problem.

Given
$T(n)=2T(2n/3)+O(n)$ prove that $T(n)=O(n^2)$.

So the steps were as follows. We want to prove that $T(n) \le cn^2$.

$$\begin{align*}
T(n)&=2T(2n/3)+O(n)  \\
&\leq 2c(2n/3)^2+an\\
&\leq (8/9)(cn^2)+an
\end{align*}$$
and then my prof went on to do:

$$T(n) \leq cn^2+(an-(1/9)cn^2)\,,$$
which comes out to:

$$T(n)\leq cn^2 \text{ for any }c >= 9a\,.$$

My question is, how were they able to switch from 8/9 to 1/9 while introducing a new term? Is this allowed? She never explained, this was just in her solutions.

As you pointed out, the reason for splitting the term into two pieces is to be able to cancel the $an$ term. If we go directly from $(8/9)cn^2 + an \leq cn^2 + an$, then we get stuck as we cannot do anything with the $an$ term. By splitting it in the way described, this allows the $(1/9)cn^2$ to be larger than $an$ when $c \geq 9a$, which then gives you the desired result since $an - (1/9)cn^2 \leq 0$ for such values of $c$.