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

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

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

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

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

# Answer
> 0 votes
I think the resolution to the paradox comes from looking more carefully what is meant when we say that multiplication can be performed in logarithmic space, and looking more carefully at what we mean by a BDD.

Suppose we want to multiply two $n$-bit numbers $a,b$, and suppose the two numbers $a,b$ are stored in read-only memory. Then we can calculate any desired bit of the product using only $O(\lg n)$ additional bits of space. However, this fundamentally requires us to have (read-only) access to the numbers being multiplied.

(Take a look at the formula in Wikipedia for $r\_i$: $r\_i$ depends on $a$, $b$, and $c\_{i-1}$. The carry $c\_{i-1}$ needs only $O(\lg n)$ bits of space to store. However, just storing the carry alone is not enough. We also need to have the numbers $a,b$ stored, and that requires $\Theta(n)$ bits of storage.)

In short, multiplying two numbers takes $\Theta(n)$ bits (read-only) for the numbers being multiplied and $\Theta(\lg n)$ bits (read-write) of additional storage. This does prove that multiplication is in $L$. However, it doesn't prove that there is a polynomial-size BDD for multiplication.

First, let's understand what we mean by BDD. There are many types of BDD, but the most relevant one here is the notion of a ROBDD (read-once binary decision diagram). A ROBDD is allowed to read each bit of the input only once. Normally, BDD means a ROBDD: for a reference, see, e.g., the Wikipedia article on BDDs, which writes "In popular usage, the term BDD almost always refers to Reduced Ordered Binary Decision Diagram (ROBDD". Moreover, the lower bound for the size of a BDD for multiplication is actually a lower bound on the size of a *ROBDD* for multiplication. Therefore, in this answer I'll assume BDD means ROBDD.

Now, here's why the above algorithm doesn't prove there is a polynomial-size (RO)BDD for multiplication. Given an algorithm with space complexity $s$ and time complexity $t$, you can construct a BDD with something like $2^s \times t$ nodes (but here $s$ must include all input bits that might be read more than once, as well as all additional storage). This means that the number of nodes in a BDD could be as much as exponential in $s$. In the case of multiplication, we have $s = \Theta(n+\lg n) = \Theta(n)$, so from the existence of the multiplication algorithm above, all we can conclude is that the size of the BDD could be (at most) exponential in $n$. This isn't enough to show that there exists a polynomial-size BDD.

What about  vs L/poly vs BDDs? I don't think it's true that just because a problem is in L/poly, that means it has a polynomial-size BDD.

Roughly speaking (ignoring uniformity vs non-uniformity), a problem is in L or L/poly if there is an algorithm that has read-only access to the inputs and uses only $O(\lg n)$ additional bits of (read-write) storage. If we also knew that this algorithm reads each bit of its input only once, then that would imply that there is a polynomial-size (RO)BDD for the problem. But if the algorithm scans back and forth over the input bits, reading them many times, then I don't *think* there necessarily exists a polynomial-sized (RO)BDD for the problem. At least, I don't know of any result that implies that. I could be missing something.

I know Wikipedia says that L/poly is "a complexity class that captures the complexity of problems with polynomially sized BDDs". I am not sure that is exactly correct.

---
Tags: complexity-theory, bdd
---


# Question
Title: What happens when many interrupt requests happen at the same time?
My initial guess is that you would have to queue the lower priority one, but what happens when for example 5 or many more requests happen at the same time? Are all these requests put in a queue or are they lost forever?

# Answer
In most cases, interrupt requests are processed, in priority order. Typically this does not involve a queue, but instead, lower priority interrupts continue to be asserted until such time as they can be processed.

A typical example would be the interrupt controller in a PC. This traditionally has a number of inputs, each assigned a priority. The peripheral signals its request. This remains until the processor clears the interrupting condition.
> 2 votes

# Answer
When multiple interrupts are generated then the action/result depends upon the type of interrupt. In Level Triggered Interrupts multiple interrupts might still be valid till the time CPU processes one of the interrupt. In case of Edge Triggered Interrupt, there are chances of interrupt loss when multiple devices interrupt simultaneously. Now why multiple interrupts are better handled in case of Level Triggered Interrupt see here "Types of interrupts".
> 2 votes

# Answer
Interrupts have priority like when system off button clicked an interrupt appear which priority so high so this is called as soon as possible.

In case of many interrupts system should be slower to handle all interrupts according to priority.

If need more examples i can explain more easily.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Restricted traversal on an undirected graph
Given a undirected graph $G=(V,E)$.

Imagine traversing the Graph was restricted; following an edge $a$ over a node $v$ to an edge $b$ is allowed if and only if a function $w: ( a, v, b ) \rightarrow \\{0,1\\}$ returns $1$.

Is there a effective solution to find the shortest path between two nodes without trying every possible path on the graph? (Since without visiting every node from every possible direction it is not guaranteed to follow every edge that might exist. Also, just remembering if a node has been already visited nor not does not fit anymore since there might be other leaving edges allowed to take - depending on the incoming edge that had been taken. )

Also, is there a more common formulation of this problem (e.g. “restricted traversal”) ?

# Answer
Yes, here's an algorithm for that. Construct a new graph $G' = (V\times V, E')$ where you have an edge $(u,v) \to (v,w)$ for each triple of vertices $u,v,w \in V$ such that $(u,v) \in E$, $(v,w) \in E$, and $w((u,v),v,(v,w))=1$. Now look for the shortest path in $G'$. This graph basically keeps track of the current node and the previous node; the node $(u,v)$ in $G'$ corresponds to a traversal in $G$ where the current node is $v$ and the previous node was $u$.

If you know finite automata, this is basically a product construction (parallel composition).
> 2 votes

---
Tags: graph-traversal
---


# Question
Title: Design Hashing function from known distribution of bits to be set
How to design Hashing function when the distribution for the bits that will be set are known before hand? Given that the number of bits to be set is constant. The intention is to minimize the hash collisions and resizing of the hash table.

Mentioned query is more of an open-ended question. What I am interested is in the known existing approach for such scenarios?

More description: Design a hashing function where the keys are formed from 64 bits. The number of bits $(l)$ that will be set is fixed which is $3 \leq l \leq 15$ of the 64 bits in the key. Further clarification, any $l$ bits in of the given 64 bit will be set.

Approximate distribution for the respective bit to be set is also known beforehand. The approximate probability of the $k^{th}$ bit will be set in the keys that will be inserted is known. In other words, for most keys that will be inserted in the hash table $k^{th}$ bit will not be set.

Implementation is to be done in C++ if this information helps in anyway.

I have tried with bit mixing from link which has the following function:

```
UInt64 MurmurHash3Mixer( UInt64 key )
  {
  key ^= (key >> 33);
  key *= 0xff51afd7ed558ccd;
  key ^= (key >> 33);
  key *= 0xc4ceb9fe1a85ec53;
  key ^= (key >> 33);

  return key;
  }

```

But the number of key collisions wasn't much affected. Also, the execution time worsened in comparison to hashing scheme that comes with `std::ordered_map`.

For my case, most of the keys have the property that last certain will never be set and the probability of initial bits will be set is lower than the bits in the middle section.

`std::ordered_map` \- I believe uses the initial bits to map to a memory location. Since, many of keys share the property more time is spent in re-hashing.

# Answer
There are 224,723,513,575,448 possible 64-bit bit-strings which satisfy the constraint that there are between 3 and 15 one-bits (inclusive). That number is approximately 247.675, so it could be represented in 48 bits. This compression is not particularly difficult, but it is much slower than the Murmur3 mixing algorithm you cite, whose speed seems to be a concern.

In any event, the compression won't really help you much (if at all). A good hash function will produced unbiased distribution of hash values for any subset of possible inputs; such hash functions are theoretically possible and, with appropriate caveats, practically achievable. (Tabulation hashing is a simple and effective technique, which is provably independent provided you have an appropriate source of randomness. But unless you have special requirements, you are probably better off using an existing hash library which has been tested and found to be unbiased.)

In practice, the C++ standard does not prescribe any particular hashing algorithm nor does it prescribe any particular mapping from hash values to buckets for *unordered associative containers* (there is no such thing as a `std::ordered_map`; there are `std::map`, which is ordered and therefore not a hash table, and `std::unordered_map`, which is a hash table). The implementations of the C++ standard library I know of use the identity function for hashes of all integer types. (Hash values are of type `size_t`, which means that values larger than the capacity of a `size_t` will be reduced modulo the size of a `size_t`; that will be the case for a 64-bit key on most 32-bit architectures.) Since that is likely to produce biased results in your case regardless of how the hash values are mapped to buckets, you probably are well-advised to use a specialized hash function, at least if you expect the hash tables to be large.
> 1 votes

# Answer
## The theoretical answer

Use a 2-universal hash function (see also here). It is provably good, regardless of the input distribution.

## The pragmatic answer

Use any good, standard hash function that mixes the bits well. You don't need a special hash function for this situation -- any standard one should be fine. The fact that you happen to know that the inputs will only have 3..15 bits set doesn't change that.

For instance, the following should all be fine: MurmurHash, Pearson hash (though it only outputs a 8-bit hash value, which might not be enough). FNV hash might be OK. I'd worry a bit more about Jenkins hash. I haven't looked at CityHash, SpookyHash, or FarmHash but they sound promising.

There *are* standard hash functions that don't mix the bits very well (perhaps on the assumption that the inputs will be random enough that this isn't needed). Don't use one of those.

You might be interested in SMHasher, a toolkit for testing candidate hash functions.
> 0 votes

---
Tags: optimization, hash-tables
---


title: DFA with less states than NFA

text:
# Question
Title: DFA with less states than NFA
Is it possible for a DFA to have less states than its equivalent NFA? Number of transitions does not matter. If possible also give an example.

# Answer
Theoretically yes, that NFA could have 9001 unreachable stats that are completely useless.

If you expect that NFA to be connected (common sense) then if you allow epsilon-moves you can have a huge useless cykle.

If you rephrase your question to:

Lets consider any Language and its 'smallest' (min number of states) NFA with $\epsilon$-moves and its 'samllest' DFA then the answer is no and the reason is simple.

any DFA is also NFA (names does not suggest that though). therefore if we take a 'smallest' NFA and then manage find equivalent DFA that is 'smaller' that would contradict previous NFA being smallest.
> 9 votes

# Answer
No. There are infinitely many NFA that are equivalent to any given DFA – it does not make sense to speak of "a DFA and its equivalent NFA". Moreover, every DFA is a very predictable NFA.
> 5 votes

---
Tags: automata, finite-automata
---


# Question
Title: Given 3 disjoint Turing-recognizable languages prove that one of them is decidable
> Let $A$, $B$, $C$ be Turing-recognizable languages over an alphabet $\Sigma$. Assume that
>
> * $A\cup B\cup C = \Sigma^\*$, and
> * $A\cap B = A\cap C = B\cap C = \emptyset$.
>
> Prove that $A$ is Turing-decidable.

So far I've tried the following but it really hasn't gotten me anywhere.

Suppose $A$ is recognizable but not decidable then, $\overline{A} = B \cup C$ so $B$ or $C$ is undecidable, since decidable languages are closed under union.

In the case that only one is decidable you can show at least that its in $A$ or $B$ (or $A$ or $C$ in the other case). Then, ... ?

In the case that both are recognizable, ... ?

# Answer
Let's call MA, MB and MC the Turing machines that recognize A, B and C, respectively. The 3-TM T (a Turing machine with 3 tapes) that decides A can be described as follows:

T: input *x*.

1. Copy x on 2nd and 3rd tapes.
2. T executes one step of MA on tape 1. If MA accepts x, T accepts x.
3. T executes one step of MB on tape 2. If MB accepts x, T rejects x.
4. T executes one step of MC on tape 3. If MC accepts x, T rejects x.

T halts for every string x in A U B U C, so T halts for every input in Σ\*. Moreover, L(T) = A. So T is a TM that decides A, and A is Turing-decidable.
> 2 votes

# Answer
$A$ is recognizable by assumption. Since $\overline{A}=B\cup C$ is recognizable (recognizable languages are closed under union) we have that $A$ and $\overline{A}$ are recognizable, and hence $A$ must be decidable (it's a simple exercise to construct a decider for $A$ from the recognizers of $A$ and $\overline{A}$).
> 2 votes

---
Tags: turing-machines, undecidability
---


title: Newbie Random NFA DFA questions

text:
# Question
Title: Newbie Random NFA DFA questions
Can't seem to answer these questions, I'm sure the answers are out there somewhere but I don't really know what keywords to use to find them. Any answers or good sites/ documentation would be much appreciated. And please don't say wikipedia, the language used is a bit out of my comprehension at this moment.

* Is it correct to assume that an NFA can be converted into multiple versions of a DFA?
* Are there different methods for doing so and would they all be considered correct assuming they give different answers?
* If an NFA has the transition relation **d{ (q0,e,q1), (q1,e,q1), (q1,e,q2) }** would it be correct to write it out as **d(q0,e,q2)**? (e standing for epsilon, q0 being initial state and q2 being final)
* Is it correct to assume that every state in an NFA has a "hidden" e transition? Essentially can you assume that every state in an NFA has an e\* transition.
* Is it bad practice when converting to have multiple NFA states as one DFA state?

Alternatively is there some way I can test my conversions out and make sure they are correct either using a program or some other way.

Apologies for the noobiness of the questions.

# Answer
> 3 votes
Answers to your questions in given order: (a) Yes, an NFA could in principle be converted into multiple distinct DFAs for the same language. Note however: There is always a unique DFA having a minimum number of states; other DFAs would have to be 'redundant' in some sense. (b) There may be different methods, though I am only aware of one. As long as the resulting DFA recognizes the same language, I would say the conversion method would be considered correct. (c) No, the expression **d(q0,e,q2)** would NOT be correct; however for every transition function **$d$** there is a corresponding *transitive closure* **$d^\*$** for which that would be a valid expression. (d) No, it is not correct to assume the existence of 'hidden' **e** transitions; all defined transitions, **e** or not, must be given explicitly, but it is permissible to leave some transitions undefined (and any NFA-to-DFA converter must handle that case). (e) Not only is it NOT 'bad practice' to have multiple NFA states as one DFA state, that is the standard tactic used by the canonical NFA-to-DFA procedure.

---
Tags: finite-automata
---


# Question
Title: Does the concept of the array pre-date physical computer memory implementations?
Does the concept of the array (a sequence of equally-sized elements accessible in O(1) time, occupying O(n) space) pre-date physical computer memory implementations?

I am trying to gauge whether computer memories were designed for the array or whether the array concept was designed to work with computer memories.

# Answer
Here's a thought. Consider the venerable spreadsheet. No, not the program, but the piece of paper. It was a regular array of cells, with column and row check sums and corner balancing for verification. They were used to hold accounting data back in the days when this was done by hand.

While not data in memory, it does embody the concept of a regular array of data.

I can't find a date on the use of paper spreadsheets, but I did find this:

> However, the spreadsheet has been in existence, as a paper based product, for longer than any of the computer based products. In the UK it was called “Multi-column analysis paper”. In the USA it was called a “spreadsheet” hence the name of the computer based version.

http://www.bygsoftware.com/Excel/Standards/SS\_801\_spreadsheetsbriefhistory.htm
> 4 votes

---
Tags: arrays, history
---


# Question
Title: Expected number of independent sets of size $k$ in random graph $G(n,p)$
I am looking for a formula for determining the expected number of independent sets of size $k$ (for arbitrary $k$) in a random graph $G(n,p)$. Here $n$ is the number of vertices and each edge is included with independent probability $p$. I would like to be able to calculate this for arbitrary $p$ if possible.

I have come across the article \[1\] which provides a formula for the special case $p = 0.5$.

I have also come across the article \[2\] which in p. 12 provides a value for some cases other than $p = 0.5$, so I would assume it is known for some $p$ values other than $0.5$.

My questions are:

1. Do you know how one shows, or could you provide a reference for the formula shown in \[1\] for the case $p = 0.5$. The paper gives some references but they are about clique problems and I am not sure how I could arrive from them to the result shown in that paper.
2. Is there a known formula for arbitrary $p$? If not, for what $p$ values is a formula known and where could I find such formulas?

---

\[1\] Chromatic and Independence Numbers of $G\_{{n}, {{1}\over{2}}}$

\[1\] Feo, Thomas A., Mauricio GC Resende, and Stuart H. Smith. “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set.” Operations Research 42, no. 5 (1994): 860–78.

# Answer
The probability that a specific set of size $k$ is independent is exactly $(1-p)^{\binom{k}{2}}$ (why?). Linearity of expectation shows that the expected number of independent sets of size $k$ is $\binom{n}{k} (1-p)^{\binom{k}{2}}$ (why?).

If you can't follow this calculation, please follow Denis Pankratov's advice and look up linearity of expectation and indicator random variables.
> 7 votes

# Answer
This is an old thread, but I thought it was worth adding: there actually is at least one paper that derives this result (or to be precise, the equivalent result of the expected number of cliques of size $k$; cliques in $G(n,p)$ correspond to independent sets in $G(n,1-p)$). It is a conference paper, "On the Complete Subgraphs of a Random Graph" by David Matula, from 1970, available here, on the author's website. It's not a hard result to derive, but someone thought it was worth publishing at least once!
> 2 votes

---
Tags: graphs, clique
---


# Question
Title: Is it computable if a particular number follows the Collatz conjecture?
I was attempting to write a computer algorithm to determine if a particular number breaks the Collatz conjecture. It is very easy to determine if a particular number falls into a loop, however I cannot think of any way to determine if a particular number is on an infinite divergent trajectory.

Assuming the Collatz conjecture is false, is it computable to determine whether or not a particular number is on an infinite trajectory?

# Answer
In short: we don't know :-)

There is a ((very) little) chance that the Collatz sequence is Turing complete (with probably some caveats like in the case of Two-counter Machines); i.e. there is an algorithm which for every turing machine $M$ outputs an $x$ such that:

$Collatz(x)$ is on a divergent trajectory if and only if $M$ doesn't halt on empty tape

in other words "deciding if a particular Collatz trajectory is divergent" could be undecidable.
> 6 votes

# Answer
First, some small tips about the testing:

The following are easily shown to be equivalent: a. The Collatz sequence reaches 1 for every starting point x ≥ 1. b. The Collatz sequence reaches a value y \< x for ever starting point x ≥ 2. This reduces the work a lot.

You need to make sure that large numbers in a sequence are handled correctly. For example, if you use 64 bit integer arithmetic and don't watch out, you will get integer overflow and therefore rubbish results for relatively small starting values.

Now it's easy if you are a bit careful to write code that tries to test if the Collatz sequence ends at 1, with the following possible outcomes: a. Your code proves the sequence ends. b. Your code notices that it encountered numbers too large for it to handle. c. Your code detects a cycle. d. Your code detects that it didn't reach 1 in a very large number of steps. e. Your code just continues running forever.

Case a is fine. In case b, you change your code. Case c disproves the conjecture. Case e has never been encountered by anyone. Case d has never been encountered by anyone with the right definition of "very large". If you find a number where you can't prove it reaches 1, that's when you need to worry about it - but it's likely it will never happen.
> -1 votes

---
Tags: computability, number-theory
---


# Question
Title: How to schedule n jobs that come at different times on 1 machine (each taking a different time to complete the task)?
Let's say I have to do n jobs, and each job can be done at or after a time T(i) (1\<=i\<=n). And we have 1 machine and the machine takes a time M to do any job whatsoever. The machine once started can be used again only after it's job is done. What's the optimal way to schedule these jobs on the machines?

# Answer
This problem lends itself to Mixed Integer Programming. The trick is to consider that there are multiple versions of each job for each machine, and you have to cover each job once.

So you can have $c\_{j,m}$ as the indicator variables that say if a job is assigned to a machine. You have to introduce a constraint that says $$\sum\_m c\_{j,m} \geq 1.$$
> 1 votes

---
Tags: optimization, scheduling, process-scheduling
---


# Question
Title: Can we prove that a time machine is impossible using the Halting Problem?
Let us take a hypothetical machine `i` which halts on the `ith` day of the month if it rains on the `ith` day of the month. Basically it describes the present.

If we put this machine in a Halting Machine it should say whether the machine would halt. i.e. whether it would rain on the `ith` day of the month.

Since the Halting Machine is not possible, a time machine is not possible.

Is there any fault in my reasoning?

# Answer
> 4 votes
When we say that no Turing machine decides the halting problem, we mean just that – the mathematical model of a Turing machine has a certain limitation, not being able to compute the halting problem. Turing machines are supposed to model what is computable in the physical world, but this is not a mathematical fact. If the physical world turns out to be richer, all results on Turing machines will still hold, it's just that their real-world interpretation will be weaker.

What you show in your question is that if time travel is possible, then Turing machines are not a good model for the notion of computation. The fact that Turing machines cannot solve the halting problem has absolutely no bearing on the reality of time travel.

Moreover, you misrepresent the Turing machine model. A Turing machine has no access to the real world, so it cannot halt if it rains on a specific day. All it has access to is its (potentially infinite) tape. In fact, Turing machines cannot be realized in full generality in the real world (since their tape is potentially infinite) – they are abstract machines which are supposed to model *some* features of reality.

---
Tags: halting-problem
---


# Question
Title: What is the different between Dijsktra's algorithm and KNN?
I am implementing machine learning software and in my case, I am using K-nearest neighbour classifier to get the task done. So far, I am trying to understand how Dijkstra's algorithm that has been used to solve salesman travel problem is different from K-nearest neighbour algorithm?

# Answer
> What is the different between Dijsktra's algorithm and KNN?

Almost everything.

**$k$ nearest neighbor is a classification algorithm**. It stores a list of `[(features1, label1), (features2, label2), ..., (features-n, label-n)]`. When it gets a new item `features` it calculates the distance to each of the $n$ stored items. It finds the $k$ closest ones. It returns the label which is most often in those $k$ examples.

**Dijkstras algorithm is a graph search algorithm.** It takes a graph $G = (V, E)$, a start node $s \in V$ and a target node $t \in V$ as input and returns the shortest path (v\_1, \dots, v\_n) with $v\_1, \dots, v\_n \in V$ from $s$ to $t$.

(You might be interested in the label correction algorithm, a generalization of Dijkstras algorithm)

## How they can be related. Somehow.

$k$ nearest neighbor can also operate on graphs. If you have a graph-like structure and your distance measure is e.g. the number of hops from a node, then you would use breadth first search.
> 2 votes

---
Tags: machine-learning, classification
---


# Question
Title: Keywords for classification of 2D time series data?
Trying to find the right search terms for literature on classifying 2D time series data.

I am looking at data from positional tracking of a swarm of insects over time. I have example datasets for specific insect behaviors, and I would like to play around with training a classifier on these.

# Answer
> 0 votes
You might be interested in RNNs (e.g., LSTMs) or Hidden Markov models. RNNs can be used directly for classification. HMMs can be used to build a generative model for each class, which can then be used for classification: if $x$ is the observed 2D time series, the model for class $c$ lets you compute $P(x|c)$, and then you can classify $x$ by selecting the class $c$ that maximizes $P(x|c)$ (the maximum likelihood principle).

# Answer
> 1 votes
The one-nearest neighbor classifier is very competitive for time series. http://www.cs.ucr.edu/~eamonn/ICML2006.pdf If you want code or data, I have lots of both. eamonn

---
Tags: machine-learning, classification, clustering, time-series-analysis
---


title: Find witnesses (or not)

text:
# Question
Title: Find witnesses (or not)
I have just started learning Analysis of Algorithms and I came across these set of questions:

1. Find witnesses c and m such that *rn+1 = O(rn)* for r\>1
2. Show that there are no witnesses for *n2 = O(n)*
3. From 2, deduce no witnesses for *22n = O(2n)*

So, I have tackled some as:

1. *rn+1 ≤ rn+1*
*rn+1 ≤ r.rn*
*rn+1 ≤ (r+1).rn*
Therefore, c = r + 1; m = 1
2. *n2* ≤ n2
No value for c satisfies the above inequality, therefore no witnesses (??)
3. *22n ≤ 22n*
No value for c satisfies the above inequality, therefore no witnesses (??)

I am not sure how to go about the last 2. Can anyone please tell me whether what I have done is correct?

Thanks.

# Answer
> 1 votes
Part 1 looks OK.

For part 2, to show no witnesses exist, you have to proceed by contradiction. Assume witnesses $c,m$ exist, so we have $n^2 \leq cn$ for all $n\geq m$. Now, to reach a contradiction, find at least one value of $n \geq m$ for which $n^2 \> cn$. The value for $n$ can be defined in terms of $c,m$. It shouldn't be too hard to find one.

For part 3, the text suggests to use 2. That is, to prove that if we had (by contradiction) witnesses for 3, we could derive from them some witnesses for 2.

(Honestly, to me this way sounds harder than simply tackling 3 on its own, without exploiting 2. Maybe you were introduced to some theorem which can apply here to shorten the exercise? I have no idea.)

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: Under which operations is the class of non-recursive languages a closure?
I am currently studying turing computability and related problems such as the halting problem with a background in formal languages.

I know that the class of recursive (decidable) languages is a closure under union, intersection and complement, and that recursively enumerable languages (semi-decidable) are a closure under union and intersection, but what about non-recursive (undecidable) languages?

To be more specific, I am trying to prove that a specific language of the form $$L = \\{ w \in \Sigma^\* : w \in A \lor w \in B \\}$$ is non-recursive. I managed to prove that neither $A$ nor $B$ are recursive by reducing them to the universal halting problem, but I am not sure what that implies for $L$.

> The exact language is $$L = \left\\{ w\\#u \in \left\\{ 0, 1, \\# \right\\}^\* | \\ M\_w \text{ will halt with input } u \text{ or } M\_u \text{ will halt with input } w \right\\}$$ where $M\_b$ is the turing machine whose transition function $\delta$ is represented using Gödel numbering as a binary string $b$.

Is the class of non-recursive languages a closure under union? If it is, how could I prove it myself or where could I find an existing proof?

# Answer
> 2 votes
Non-recursive languages are closed under complement, but not under union or intersection.

Indeed, a decider for $A$ exists iff there is a decider for $A^c$. Hence the closure under complement.

However, let $B$ be any non-recursive language. $B^c$ is also non-recursive. But $B \cap B^c = \emptyset$ and $B \cup B^c = \Sigma^\*$ are both recursive. Hence, non-recursive languages are not closed under union or intersection.

In the example you mention, you can not conclude anything about $L$ from $A,B$ being non recursive.

I will provide a hint for $L$, only. When you have a language of the form $L=\\{f(x,y) | x,y\mbox{ s.t. } p(x,y)\\}$, it is sometimes convenient to choose a particular value $a$ and study the related language $L\_a = \\{ y | y\mbox{ s.t. } p(a,y) \\}$ first. Maybe one can choose $a$ to make $p(a,y)$ simple enough so that other proof techniques apply.

---
Tags: formal-languages, turing-machines, closure-properties, halting-problem
---


title: Linear Bound Automaton Power

text:
# Question
Title: Linear Bound Automaton Power
Please tell me is their deterministic linear bound automaton same power as non-deterministic linear bound automaton to recognize any language?

# Answer
> 2 votes
Your question is equivalent to asking whether or not $DSPACE(O(n)) = NSPACE(O(n))$, which is an open problem, known as the first LBA problem.

---
Tags: proof-techniques
---


# Question
Title: How would one construct conjunctively local predicate of order k for checking if a shape is Convex?
I was reading Minsky's and Papert's book on perceptrons and it had the definition of conjunctively local as follow (look at the last images if its still unclear):

A predicate $\psi$ is conjunctively local of order k if it can be computed by independently computing a set of functions $\varphi\_1(X)$...$\varphi\_n(X)$ and then combined by the results of another function $\Omega$ of n argument by a set $\Phi $ of predicates $\varphi$ such that each $\varphi$ depends no more than $k$ points on a 2D Euclidean plane $R$ and: $$ \psi(X) = \begin{cases} 1 \text{ if } \varphi(X) = 1 \text{ for every } \varphi \text{ in } \Phi \\ 0 \text{ otherwise. } \end{cases} $$

Then in the book they claim that testing if a figure $X$ drawn on a 2D Euclidean pixel plan $R$ is conjunctively local of order 3. First recall how one would text for convexity on $R$. Essentially one woul look at three points/pixels and draw a line segment joining the points and if the third chose point between them is not in the drawn figure $X$, then it would not be convex.

My question is given this knowledge, how does one show that $\Psi\_{convex}(X)$ is conjuctively local of order 3? The order 3 seems sort of clear to me because each $\varphi$ only needs look at 3 points to test convexity. However, it remains unclear to me how one would construct a general $\Psi(X)$ such that it always test correctly for any drawn geometric shape if its convex or not. I guess maybe part of my quesiton is that the definition of conjuctively local is not clear to me. Is it correct to think of $\Psi$ as a function only on the given geometric shape or is it also a funciton fo the whole plane $R$? It seems clear how to construct $\Psi$ if we know the shape in advance but otherwise it doesn't seem we can fix one single architecture and be able to text for convexity.

---

# Answer
> 3 votes
One way to construct $\Psi\_{\mathrm {CONVEX }}$ is as follows: define $\phi\_{i,j,k}(X) := \begin{cases} 1 & \text{if $(x\_i,x\_j \in X \Rightarrow x\_k\in X)$ } \\ 0 & \text{otherwise}\\\end{cases}$.

Now, we define the set $\Phi$ by picking all pairs of $x\_i,x\_j\in R$ and all $x\_k$ that lie on the line segment between them, i.e. $\phi\_{i,j,k}\in \Phi$ for all $x\_i,x\_j\in R$ and all $x\_k\in \\{x\in R\mid \exists\lambda\in \[0,1\]: x=\lambda x\_i + (1-\lambda)x\_j\\}$.

Note that each $\phi\_{i,j,k}$ depends on only three values of $R$ and that the shape $X$ is convex if and only if all $\phi\_{i,j,k} \in \Phi$ have value $1$. So, according to your definition, $\Psi\_{\mathrm {CONVEX }}$ is conjuctively local of order $3$.

This does not seem like a very practical approach to determine the convexity of a shape, in particular when $R = \mathbb{R}^2$, since that means $\Phi$ is of infinite size.

So the basic idea is that for given indices $i,j,k$, the $\phi\_{i,j,k}$ are functions of $X$ and exactly three points of $R$: $x\_i,x\_j$ and $x\_k$. The selection of their indices (i.e. the set $\Phi$) is independent of $X$, but does depend on $R$.

---
Tags: algorithms, logic, artificial-intelligence
---


# Question
Title: Class of languages that are equivalent to the lambda calculus
It is well known that all computable functions can be expressed as terms of the lambda calculus and computed according to its rules. It is also more or less obvious that many classical formal languages (i.e. languages with formalized semantics) can be translated into the lambda calculus (e.g. using a Church encoding). I am, however, pretty sure that there are languages where such a translation is not possible, the simplest example would be a language with a builtin primitive that solves the Halteproblem.

That makes me wonder if there is an established terminus for the languages that can be translated.

Is there a name for the class of languages that can be translated (correctly, completely) into the lambda calculus?

# Answer
> 5 votes
The lambda calculus is exactly equivalent in expressive power to Turing machines, so the languages that can be translated into it are exactly those that are no more powerful than Turing machines.

Models of computation that are more powerful than Turing machines are known as "hypercomputation". However, except for computability theorists, most people don't ever consider languages that can express hypercomputation, so most people don't need a word that "not capable of hypercomputation." It's a bit like there being no word for "food that isn't poisonous" because not being poisonous is the default state for food so people don't really need a word for that.

Your question title asks about languages that are equivalent to the lambda calculus, i.e., those where we can translate in both directions. Because the lambda calculus has the same power as Turing machines, these are exactly the Turing-complete languages.

---
Tags: computability, terminology, lambda-calculus
---


# Question
Title: Covering the unit square by smaller squares of variable sizes
I'm trying to find whether a property $\mathcal{P}$ is true for all points of the unit square (in 2D). At each step I can query for a point of my choice. An oracle then answers me by either:

* telling me $\mathcal{P}$ doesn't hold for this point and thus the problem is solved: the property doesn't hold for all points in the unit square.
* tells me $\mathcal P$ holds for not only my query point but also for a small square containing my point. Thus I don't need to query for other points in this small square.

The problem is the small squares returned by the oracle are of variables sizes. What data structure and algorithm can I use to store the small squares returned? How can I track efficiently whether I have enough small squares to cover the unit square (and can thus stop the algorithm since I know the property holds for the whole unit square)? Or compute new points to query?

Edit: Okay, I realized my description of the problem is over-complicated. Basically this is the problem:

I have a certain number of squares of variable sizes and positions. How do I check whether they completely cover the unit square, or if not, how do I obtain the coordinates of a point of the unit square not covered ? PS: The problem is online.

# Answer
> 1 votes
I'd suggest a 2-dimensional k-d tree storing one point for each corner of each rectangle returned. A quadtree or 2-dimensional interval tree might also work. More generally, you might consider a 2-dimensional binary space partitioning tree, where you partition based on one of the edges of one of the squares returned (extended horizontally or vertically out to infinity in both directions).

How would you partition, in a binary space partitioning tree? Each square gives you two horizontal lines and two vertical lines (obtained by extending each edge of the square out to the full unit square). For instance, imagine sorting all of those vertical lines from left-to-right, and picking the median line, and using that to partition. Continue splitting recursively. This gives you a nested tree of regions. Then, associate each square with the lowest (deepest) node/region that fully contains it. When you are picking a split for a particular region of space, you use all of the lines that fall within that region (from all squares that have any overlap with that region).

# Answer
> 1 votes
I think a 2-dimensional (compressed) Quadtree can be useful here.

If you store a new rectangle in the tree, you can subdivide the space in the rectangle such that the boundary of the new rectangle does not lie in the interior of any subdivision, but lies only on the boundary of the subdivision. Checking whether there exists a 'non-covered' point can be done by storing the 'non-covered' as satellite data.

If you remove a rectangle from the tree, you need to check only for all 'quads' that the rectangle covered whether there exists (new) uncovered points.

---
Tags: algorithms, data-structures, computational-geometry
---


# Question
Title: Using DCEL to represent "simple geometric objects"
Many algorithms in computational geometry assume to have as input a complex data structure to represent a geometric object. The most common I know is the Doubly connected edge list, but there're also the halfdge data structure, winged edge etc... I was wondering if such data structure is also used to represent simple object. I know for example there's no need to represent a vertex or a line segment using a DCEL, however in practical implementations this would probably make the interface reusable, and therefore the whole algorithm implemented (unless we want to use some wrapper but I'm assuming I'm not).

So my question is, how can both points and segments be represented using a DCEL?

I would initialize the `half_edge_incident` field to be `NIL` and I would keep the  `list_< HalfEdge* >`  empty, same as the `list< Face* >`?

For the segment case I would just have two vertices entries not empty, two half edges entries not empty, the faces list would be empty.

Does this representation work?

# Answer
> 1 votes
First of all, while being generic is nice from an user perspective, it is usually the best idea to use the simplest structure that you require from an algorithmic perspective. The proper solution to this problem is simply to offer the user a single interface (or 'wrapper', as you call it).

(Another problem is that unnecessary abstraction is potentially unbounded. Why use a plane when $\mathbb{R}^n$ is more general? Why use that when an abstract metric space is more general, etc.)

Now, for your specific construction:

> For the segment case I would just have two vertices entries not empty, two half edges entries not empty, the faces list would be empty.

The problem with this construction is that a lot of fields are empty that I would expect to be filled. Why do some edges have no face, why do some edges have no successor? Both these cases do not occur in a DCEL, so to make this particular structure work you must already define a generalisation of a DCEL that allows for empty fields. Most importantly, you are trying to store something that is **not** a *subdivision of the plane* in a DCEL, which is designed to store precisely that!

If you really want to store 'simple geometric objects' in the plane, using a trapezoidal decomposition seems like a decent idea, as it can reasonably store both segments and polygons. (It is even possible to store both a trapezoidal decomposition and a DCEL for the same data) However, this all depends on the actual application, since some operations are more efficient with a DCEL or other structures.

If you insist on storing segments in a DCEL, an approach is to represent a segment by a pair of edges (so 4 half-edges), where one of the 'faces' is the space surrounding the segment and the other the face 'inside' the segment (with 0 area).

---
Tags: data-structures, computational-geometry
---


# Question
Title: Is true that $L_1 = \{01^*0\}$ is $m$-complete in the class of decidable languages?
**Question:**

> Is true that $L\_1 = \\{01^\*0\\}$ is $m$-complete in the class of decidable languages?
>
> $L\_1$ is defined as:
>
> $$L\_1 = \\{01^\*0\\} := \\{01^n0: n \in \mathbb{N}\\}$$

**Definition of a $m$-complete language:**

> A language $L^\*$ is $m$-complete in the class of decidable language, if for any decidable language $L$ we have that $L \leq\_m L^\*$ (that is, $L$ reduces to $L^\*$).

I'm really new in this realm, so I'm quite lost about how to tackle this exercise.

I'm not sure if my approach is correct but I was trying to prove that the statement *is not true* by using a reduction from the Busy Beaver Function to $L\_1$ (then, from this reduction and from $L\_1$ being decidable we would have that BB problem is decidable, which is not possible).

Let $A$ be the algorithm deciding $L\_1$ and $w \in L\_1$ a word with $|w| = m$ ones. Now when running $A$ on $w \in L\_1$ we keep track of the number of steps $t$ it made just before halting. Since $t = m|\Gamma|^m|Q|$, where $\Gamma$ is the set of tape symbols and $Q$ is the set of states. From here we can find the number $|Q|$ of states required for printing $|w| = m$ ones...

I stopped here because I feel there is already something wrong.

First, even is we find that number $|Q|$ for which $A$ performed $t$ steps before $A(w) = \text{Accept}$, that does not necessarily mean that $|w| = m$ ones could have been achieved with a TM with lesser number of states. Second, ''knowing'' the numbers of ones I'm determining the numbers of states and not the other way around, which is as $BB$ is defined.

Another alternative I was exploring was, on input $w$, to run all TM's $T\_1, ... T\_n$, that return $|w| = m$ ones. Then we record the input $w$ and the description of the machine $T\_i,\ (i \in \[1,n\])$, that had the least number of states. If we do this $\forall w \in L\_1$, we end up with a UTM $T'$, such that:

$$T' = \\{ \langle T^\*, w\rangle: |Q|\_{T^\*} = \mathrm{min}(|Q|\_{T\_1}, ..., |Q|\_{T\_n}\ \text{}\\}$$

Then clearly $T'$ decides $L\_1$ (just have to run it on input $w \in L\_1$) and at the same time allows us to compute $BB(n)$ for a fixed $n \in \mathbb{N}$ (since $n$ is encoded in the description of $T^\*$).

Probably here there are some flaws in my reasoning, but in this case, do I have to wait that, on input $w$, all those TM's reach a halt or can I assume that the first machine that halted is the one with the least number of states?

I'd appreciate any help.

# Answer
> 1 votes
Your approach can't succeed. You're asked whether every decidable language reduces to $L\_1$ but your approach is to try to show that some undecidable language doesn't reduce to it. That would show nothing about decidable languages.

But are you sure that your definition is correct? Every language except $\emptyset$ and $\Sigma^\*$ is $m$-complete by the definition you give.

---
Tags: computability, turing-machines, reductions
---


# Question
Title: What do `i` and `Number` represent in the Bakery Algorithm?
I am studying the bakery algorithm, and I am unsure of what the variable `i` represents in it. I understand that `Entering` represents a `bool` value to protect `Nummber` while it is updating, but I'm having a hard time finding clear explanations as to what variable is doing what.

Is `Number` an array of threads? Is `i` a particular thread? Or the value being updated?

1. What do `i` and `Number` actually represent?
2. What is passed in via `Thread(integer i)`? The value we are locking? Or a thread ID number?
3. Is there a value that represents a value being locked?

For reference, here is the Bakery Algorithm I am referencing, from Wikipedia:

```
   // declaration and initial values of global variables
   Entering: array [1..NUM_THREADS] of bool = {false};
   Number: array [1..NUM_THREADS] of integer = {0};

   lock(integer i) {
       Entering[i] = true;
       Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
       Entering[i] = false;
       for (integer j = 1; j <= NUM_THREADS; j++) {
           // Wait until thread j receives its number:
           while (Entering[j]) { /* nothing */ }
           // Wait until all threads with smaller numbers or with the same
           // number, but with higher priority, finish their work:
           while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }
       }
   }

   unlock(integer i) {
       Number[i] = 0;
   }

   Thread(integer i) {
       while (true) {
           lock(i);
           // The critical section goes here...
           unlock(i);
           // non-critical section...
       }
   }

```

# Answer
As the Wikipedia page says, (emphasis mine),

> Lamport envisioned a bakery with a numbering machine at its entrance so **each customer is given a unique number**. Numbers increase by one as customers enter the store. A global counter displays the number of the customer that is currently being served. **All other customers must wait in a queue until the baker finishes serving the current customer and the next number is displayed**. When the customer is done shopping and has disposed of his or her number, the clerk increments the number, allowing the next customer to be served. That customer must draw another number from the numbering machine in order to shop again.
>
> According to the analogy, the "customers" are **threads, identified by the letter `i`**, obtained from a global variable.
> 1 votes

---
Tags: threads
---


# Question
Title: Expected weight of euclidean minimum spanning tree on a unit square
Suppose I randomly generate $n$ points from the unit square $\[0,1\]^2$, form a complete graph in which the weight of each edge is just the Euclidean distance between its endpoints, and compute the minimum spanning tree. I noticed empirically that the expected weight scales like $\sqrt{n}$. Using only back of the envelope arguments, how could I derive the $\sqrt{n}$ asymptotic behavior?

When I repeated the experiment in the unit cube $\[0,1\]^3$, the expected weight scaled like $n^{2/3}$, and when I repeated it on the unit hypercube $\[0,1\]^4$, the expected weight scaled like $n^{3/4}$. How could I derive this asymptotic behavior?

# Answer
> 2 votes
The following is based on J. Michael Steele's paper proving the rigorous bound.

The pigeonhole principle shows that out of any $n$ points in $\[0,1\]^d$, there are two at distance at most $O(n^{1/d})$, say at most $c\_d n^{1/d}$; the idea is to divide $\[0,1\]^d$ into small enough boxes, and find a box containing two points. Construct a spanning tree by repeatedly adding an edge corresponding to the two closest points and throwing out one of them. This spanning tree has cost at most $$ c\_d (n^{1/d} + (n-1)^{1/d} + \cdots + 2^{1/d}) \leq c\_d \int\_2^{n+1} x^{1/d} \\, dx = O(n^{(d-1)/d}). $$

For the lower bound, a similar argument dividing $\[0,1\]^d$ into small boxes shows that for any $\epsilon \> 0$, with probability $1-\epsilon$ there are only $\epsilon n$ many edges whose weight is $O\_\epsilon(n^{1/d})$, and so with constant probability any spanning tree has cost $\Omega\_\epsilon(n^{(d-1)/d})$. With more work, it follows that the expected weight of a minimum spanning tree is $\Omega(n^{(d-1)/d})$.

---
Tags: minimum-spanning-tree, random-graphs
---


# Question
Title: What is the simplification of AB + BC + (~B)C?
AB + C is not the answer. The correct answer is AB + BC. HOW?

# Answer
Imo there is a problem in the proposed options. Indeed,

$AB+BC+(\neg B)C=AB+(B+\neg B)C=AB+C$

You can check that also comparing the truth-tables of $AB+BC+(\neg B)C$ and $AB+C$.
> 1 votes

---
Tags: boolean-algebra, propositional-logic
---


# Question
Title: In the Resolution equivalence ($\neg A \implies B, B \implies C \models \neg A \implies C$) must $A$ be negated?
The sheet of equivalences given to us in class provides the the equivalences

\begin{array}{|c|c|c|} \hline \text{Resolution} & A \vee B, \neg B \vee C \models A \vee C & \neg A \implies B, B \implies C \models \neg A \implies C \\ \hline \end{array}

I noticed that the $A$ is negated. **Is this necessary for proper Resolution?** Or is this just an example that $A$ can be negated?

To me it makes logical sense that $A \implies B, B \implies C \models A \implies C$, but being somewhat new to the subject matter I would like to ensure that $\neg A$ is not necessary for Resolution.

# Answer
The answer is yes. But the departure point is slightly different. Here it is:

\begin{array}{|c|c|c|} \hline \neg A \vee B, \neg B \vee C \models \neg A \vee C & A \implies B, B \implies C \models A \implies C \\ \hline \end{array}

The former statement is just the fact that if you start with $A\vee B$ and turn it into an implication you find $\neg A\implies B$.
> 2 votes

---
Tags: logic, first-order-logic, propositional-logic
---


# Question
Title: If P = NP, then how not cannot solve NP-hardness (the one that doesn't intersect with NP-complete) in polynomial-time?
My question is that if P = NP, then we can solve any NP-hard problems (the one which is NP-complete and the one which is not-NP-complete) by saying that since we have a polynomial time algorithm to solve the NP problems and since the reduction works in polynomial time. Therefore, polynomial to polynomial is polynomial, and so we can solve any NP-hardness problem. For example, we can solve the TSP by calling to an NP-complete problem which have polynomial time since P=NP, and since the reduction is polynomial time, therefore we can solve TSP in polynomial time.

> How could disprove this argument? What is the clue to say that NP-hardness(the one which doesn't intersect with NP-complete) can not be solved in polynomial time even if P=NP.

I know that if P = NP, then we can only solve any problem in NP (but not in NP-hard). But I want to know what it makes NP-hard (the one that have no intersection with NP-complete) is not solvable in polynomial time even if P=NP since we have polynomial time reduction and polynomial time algorithm given P=NP.

Thank you

# Answer
You have your reductions the wrong way around. A problem $X$ is **NP**-hard if every problem in **NP** can be reduced *to* $X$. That is, saying that $X$ is **NP**-hard means that, if we had an efficient algorithm for $X$, we would have an efficient algorithm for every problem in **NP**: $X$ is easy implies all of **NP** is easy.

So, suppose that **P$\\,=\\,$NP**. Then, all of **NP** is easy, but that tells us nothing about $X$, because the implication goes the wrong way. Maybe $X$ is easy; maybe it's hard. In fact, some **NP**-hard problems are definitely hard: the halting problem is **NP**-hard but it's undecidable, regardless of what the relationship between **P** and **NP** turns out to be.
> 2 votes

# Answer
I suppose one could potentially "disprove" that argument by proving P=NP,
since as David mentions, the halting problem is NP-hard and undecidable.

Your argument is like

> If Goldbach's conjecture is true then
> we can fit (10^(10^100))+1 items into 10^(10^100) holes
> without any hole having more than one item
> by saying that since 10^(10^100) is a sum of two primes and since the primes are odd.

:
Namely,  "we have a polynomial time algorithm to solve the NP problems and"
"the reduction works in polynomial time"  follow from your assumption,
but your attempted conclusion simply does not follow from  "we have a polynomial time
algorithm to solve the NP problems and" "the reduction works in polynomial time" .
> 0 votes

---
Tags: complexity-theory, np-hard, p-vs-np
---


# Question
Title: What is the difference between radix trees and Patricia tries?
I am learning about radix trees (aka compressed tries) and Patricia tries, but I am finding conflicting information on whether or not they are actually the same. A radix tree can be obtained from a normal (uncompressed) trie by merging nodes with their parents when the nodes are the only child. This also holds for Patricia tries. In what ways are the two data structures different?

For example, NIST lists the two as the same:

> **Patricia tree**
>
> *(data structure)*
>
> Definition: A compact representation of a trie in which any node that is an only child is merged with its parent.
>
> Also known as radix tree.

Many sources on the web claim the same. However, apparently Patricia tries are a special case of radix trees. Wikipedia entry says:

> PATRICIA tries are radix tries with radix equals 2, which means that each bit of the key is compared individually and each node is a two-way (i.e., left versus right) branch.

I don't really understand this. Is the difference only in the way comparisons are made when doing look-ups? How can each node be a "two-way branch"? Shouldn't there be at most `ALPHABET_SIZE` possible branches for a given node?

Can someone clarify this? For practical purposes, are radix tries typically implemented as Patricia tries (and, hence, often considered the same)? Or can no such generalizations be made?

# Answer
I found this post very helpful.

To see the difference between Patricia tries and radix trees, it is important to understand:

* The notion of **radix**, since Patricia tries are radix trees with radix equal to 2.
* The way keys are treated: as **streams of bits**. Keys are compared $r$ bits at a time, where $2^r$ is the radix of the trie.

Suppose that we insert the keys *smile*, *smiled*, and *smiles* (in this order) in a Patricia trie. The binary representation of these keys is the following:

Note that *smile* is a prefix of *smiled*, and, analyzing the binary representation, we can see that the first bit that differs (from left to right) is **0** (highlighted in red in the second row); for this reason, *smiled* will be the **left child** of *smile*. Similarly, *smiles* will be the **right child** of *smiled* because they share the same prefix up to a bit whose value is **1** (highlighted in red in the third row). The resulting Patricia trie after inserting the three keys is the following:

If the radix was, for example, 4, then internal nodes could have, at most, four children (with their edges labeled 00, 01, 10, and 11, respectively). In this case, keys would be compared by chunks of 2 bits, and not 1 (as in Patricia tries).

---

> In what ways are the two data structures different?

To my understanding, the only difference is the radix, which is equal to 2 in the case of Patricia tries. This value can be any power of 2 in regular radix trees.

> Is the difference only in the way comparisons are made when doing look-ups?

In both data structures, the comparison operation is bitwise. However, the number of bits that are checked atomically varies according to the radix. In the case of Patricia tries, bits are compared individually (since radix = 2). This is not necessarily the case in radix trees. In general, bits are checked in chunks of size $\log\_2{R}$, where $R$ is the radix of the trie.

> How can each node be a "two-way branch"? Shouldn't there be at most `ALPHABET_SIZE` possible branches for a given node?

The radix establishes the maximum number of children that the nodes of a radix tree can have. For example, when radix = 2, each node can have at most two children. This is the case of Patricia tries (also known as binary radix trees).

> Are radix tries typically implemented as Patricia tries (and, hence, often considered the same)? Or can no such generalizations be made?

To be honest, I do not have an answer for this question. It seems that both data structures were proposed around the same time by different authors. For historical reasons that I am unaware of, both terms still live today.
> 36 votes

# Answer
A Patricia trie is a binary radix trie resulting from the application of the PATRICIA algorithm to alphnumeric data.

PATRICIA stands for *Practical Algorithm To Retrieve Information Coded in Alphanumeric* \[original paper by Donald R. Morrison\]. The paper defines a basic vocabulary consisting of START, STOP, END, L-PHRASE, BRANCH, TWIN, and CHAIN. PATRICIA tries are the tries that result from application of this algorithm - binary radix tries where the radix, r, is 2 \[wikipedia\] (and above); a binary choice at each node when traversing the trie).

However, in practice, the term Patricia seems to be used with r\>=2 (i.e radix tries), where a similar storage and search alogorithm is used. For example this is titled as patricia. The Ethereum Patricia Merkle Trie is another example, where r is 16 at certain nodes.
> 3 votes

---
Tags: data-structures, trees
---


title: Reduction from PARTITION to 3PARTITION

text:
# Question
Title: Reduction from PARTITION to 3PARTITION
I'm considering the problem (a variant of 3-PARTITION, see here) with description

> **Instance:** Set of positive integers $A={w\_{1},...,w\_{n}}$ with $S(A)=\sum\limits\_{i=1}^{n}w\_{i} = 3m$.
> **Question:** Is there a partition of $A$ into 3 subsets $A=A\_{1}\cup A\_{2}\cup A\_{3}$ such that $S(A\_{1})=S(A\_{2})=S(A\_{3})$?

I plan to give a reduction from simple PARTITION (into two subsets with equal sum) to this problem that is going like this.

a) Observe that if there is no $A'\subset A$ with $S(A')=2m/3$ then $A$ can't be partitioned into 3 subsets with sum equal to m. (because the premise implies that there's also no subset of A with sum equal to m).

b) Build an instance for PARTITION by taking a subset $A'$ of A with $S(A')=2m/3$. If it is a correct instance of PARTITION then it can be partitioned into sets $B,C$ which combined with $A\setminus A'$ produce a correct instance for the problem 3PARTITION. The other way round (correct instance for 3PARTITION --\>correct instance for PARTITION) can be proved by equally simple arguments.

Is this reduction polynomial? I mean, the choice of $A'$ is arbitrary and itself is a correct instance for the problem of SUBSET-SUM for A with target value equal to $2m/3$ which is hard to compute. If this computation plays a part in the transformation then the latter can't be polynomial, right?

# Answer
I guess that this question should not be left floating around unanswered.

The reasoning in (b) can't be used to prove that this problem is NP-complete because, at best, it implies the reduction from 3PARTITION to PARTITION which is of no use. Any problem in NP can be reduced to PARTITION.

The proper way of doing this (after showing that the problem is in NP) is to:
**i)** Start from an arbitrary instance of PARTITION
$A=w\_1,...,w\_n$ with $S(A)=\sum\limits^{n}\_{i=1}w\_{i}=2m$
**ii)** Append $m$ to $A$ and obtain $A'$, an instance of the 3PARTITION problem.
**iii)** Prove that $A\in PARTITION\Longleftrightarrow A'\in 3PARTITION$
**iv)** Conclude that $PARTITION \leq\_{p}3PARTITION$
> 1 votes

---
Tags: complexity-theory, np-complete, reductions, partitions
---


# Question
Title: Worst case using the first fit $2$-approximation for the bin packing problem
I am with the phone so I would be more verbose when I will have a pc on hand, if you desire.

The first fit algorithm for approximating the bin packing problem (NP-hard) is a $2$-approximation for the optimum. Can you show me a concrete worst case showing that $2$ is a good (or bad) extimate for the bound?

# Answer
> 2 votes
The approximation ratio of first fit for bin packing is actually 1.7 rather than 2. See Dósa and Sgall, First fit bin packing: a tight analysis. The paper contains references which prove a matching lower bound.

# Answer
> 0 votes
Just so you can check yourself that the approximation ratio will be better than 2: Assume you have items that can be fit into k bins, each bin having capacity one. So far you have used 2k-1 bins, so you want to prove that the next item fits into one of the 2k-1 bins.

Let the next item have size c. We have c ≤ 1/2: If c was greater than 0.5, then we would have 2k items \> 0.5 for a total size \> k, which couldn't fit into k bits.

And there is a bin that contains at most 1 - c so the next item fits into that bin: Otherwise, we have 2k-1 bins containing \> 1-c ≥ 1/2, so we have more than 2k-2 bins containing 1/2, 1 bin containing more than 1-c, plus an item of size c, for a total \> k. This doesn't fit into k bins.

---
Tags: optimization, np-hard, approximation
---


# Question
Title: Kraft's inequality and Shannon's noiseless coding theorem for an encoding
A discrete memoryless source **W** has words $w\_1,w\_2,w\_3,w\_4,w\_5,w\_6$ that occur with probablilities $0.05,0.05,0.15,0.2,0.25,0.3$ respectivley.

Does there exist a compact instantaneous binary encoding for this source with word lengths $2, 2, 4, 4, 5$ and $5$?

Shannon's Noiseless coding theroem that says a compact encoding has expected wordlength $n$ where $n\leq \frac{H(W)}{\log\_2(D)}$. I get $H(W)=2.328$ and $n=1.901$, but in this case the expected word length is $3.67$ so it cannont be a compact encoding.

I feel like I have gone wrong here, could somebody tell me how? Because I have gone on to the next question where I perform Huffman coding to achieve a compact instantaneous encoding however the word length for this encoding is *still* higher than $1.901$ so fee like I must have my value for $n$ wrong but can't see how?

# Answer
I don't know what a "compact instantaneous binary encoding" is, but I'm guessing it's a prefix code that saturates Kraft's inequality. If so, your numbers don't correspond to a *compact* prefix code, since $1/4+1/4+1/16+1/16+1/32+1/32 \< 1$.

Shannon's noiseless coding theorem states that when optimally encoding *large blocks*, in the limit the average encoding size per data item is the entropy. You can prove the upper bound part of the theorem using Huffman coding *applied to large blocks*. Huffman coding produces a code whose average bit length is at most $H(X)+1$, where $X$ is the source. If you use Huffman coding on blocks of size $n$, the average bit length per data item becomes $H(X)+1/n$ (why?), and by letting $n\to\infty$, you can get as close to the entropy as you want.
> 3 votes

---
Tags: information-theory, coding-theory, entropy, huffman-coding
---


# Question
Title: Should I describe automata before describing grammar?
Let's say I want to describe some new grammar formalism, which doesn't coincide with known grammar sets. Should I always previously describe corresponding equivalent automata and why?

# Answer
> 3 votes
In mathematics, the only thing that you absolutely must do is prove every theorem. Everything else is optional. In this case, you are asking whether every grammar formalism must be accompanied with a corresponding machine model. There is no such requirement, simply because not all grammar formalisms have a corresponding machine model which is natural. It is just a "nice to have" feature. More generally, the definition of a new class of languages is more convincing if the class can be defined in many seemingly different ways.

Another thing which you don't have to do but is "nice to have" is discussing closure properties of your class of languages, discussing the complexity of the classical decision problems for your class, and relating your class to other classes of languages. This is how people have studied language classes in the past, and so you would be expected to do it.

---
Tags: formal-grammars
---


# Question
Title: Explanation of proof of why connectedness is not conjunctively local of any order $k$
I was reading Minsky's and Papert's book on perceptrons and I was reading theorem 0.6.1 and I was having a hard time understanding it. The theorem was about proving that the property "connected" was not a local property i.e. that you somehow had to see the whole picture to know if something was connected or not. In particular their prove shows that "connected" is not a conjunctively local property of any order (for definition of conjunctively local see appendix at the end of this question).

In particular goes as follows:

Suppose that $\psi\_{CONNECTED}$ has order K. Then to distinguish between these two $k+1$-wide figures:

there must be some $\varphi\_0$ such that $\varphi\_0(X\_0) = 0$, because $X\_0$ is not connected. All $\varphi$'s have value 1 on $X\_1$, which is connected. Now $ \varphi\_0$ can depend on at most $k$ points, so there must be at least one middle square, say $S\_j$, that does not contain one of these points.

This last sentence is the one that does **not** make sense to me. Why does there must be at least one middle square that does not contain one of these points? I don't understand this. When it says "these points" what does that mean? Why are we talking about the middle points? Why does that matter? Also, the sentence as a whole doesn't make sense to me nor its purpose.

Like the first two properties make sense:

1. of course there must exist a $\varphi\_0$ that rejects $X\_0$, since $\psi\_{CONNECTED}$ can only work properly if **all** of its predicates say YES if and only if the shape is connected. Since $X\_0$ is **not** connected then some predicate must reject it. That is clear.
2. For a similar reason its obvious that all the predicates say YES on $X\_1$ since its connected. More precisely, that is the definition of connected according to $\psi\_{CONNECTED}$, that all its predicates say YES. Since $X\_1$ is connected then all its predicates must say YES.
3. Last part that does make sense before my brain gets confused is that of course $\varphi\_0$ can depend on at most $k$ points. This is obvious from the definition of $\psi\_{CONNECTED}$. i.e. we assume $\psi\_{CONNECTED}$ is conjunctively local of order $k$ so all of the predicates $\varphi$ can only see $k$ points.

however, the existence of $S\_j$ doesn't make sense to me and thus, the remaining of the proof remains a mystery to me. If anyone can clarify that and the remains of the proof that would be fantastic!

Also, for completion, the whole proof is provided in the appendix2.

---

Appendix::

Recall the definition of Conjunctively local:

A predicate $\psi$ is conjunctively local of order k if it can be computed by independently computing a set of functions $\varphi\_1(X)$...$\varphi\_n(X)$ and then combined by the results of another function $\Omega$ of n argument by a set $\Phi $ of predicates $\varphi$ such that each $\varphi$ depends no more than $k$ points on a 2D Euclidean plane $R$ and: $$ \psi(X) = \begin{cases} 1 \text{ if } \varphi(X) = 1 \text{ for every } \varphi \text{ in } \Phi \\ 0 \text{ otherwise. } \end{cases} $$

or directly from Minsky's and Papert's book:

---

Appendix 2:

Proof of theorem 0.6.1

# Answer
> 5 votes
The predicate $\varphi\_0$ depends on at most $k$ points. There are $k+1$ middle squares. So $\varphi\_0$ cannot depend on all of them. That is, there is a middle square that $\varphi\_0$ does not depend on. Therefore, if we add that square, the value of $\varphi\_0$ doesn't change, and so $\psi$ is still 0, even though the figure is now connected.

# Answer
> 3 votes
For the sake of an exercise I want to explain my understanding (and to provide a alternative explanation).

When $\psi\_{CONNECTED}$ computes whether something is connected or not, each predicate $\varphi\_i$ can only see at most $k$ squares/pixels. Therefore, we define $\varphi\_0$ to be the predicate that returns 0 on the not connected figure $X\_0$. Note that even in the "best case" $\varphi\_0$ can never process all the middle points that separate the strips of $X\_0$ (because $\varphi\_0$ can only see at most $k$ squares/pixels and the shape $X\_0$ is of length $k+1$, so it will always miss at least one square/pixel). Therefore, there will always be some middle square $S\_j$ that is **not** processed by $\varphi\_0$. Therefore, if we make this square connect the top and bottom strips of $X\_0$ and call this new figure $X\_2$, then this new figure presents a problem. The problem is that its a figure nearly identical to $X\_0$ but that its connected. Note this means that $\varphi\_0(X\_0) = 0 $ but it also return $\varphi\_0(X\_2) = 0$ (but it should return 1). Why? because it doesn't matter which squares/pixels $\varphi\_0$ process, it will process them identically in both $X\_0$ and $X\_1$. The only chance for it to process them differently for $X\_2$ than in $X\_1$ is if $\varphi\_0$ processed $S\_j$. However, $X\_2$ was constructed such that $\varphi\_0$ messed up and did **not** process $S\_j$. Thus, this presents a contradiction. There is one shape $X\_2$ where our big predicate $\psi\_{CONNECTED}$ says not connected when it is in fact connected. Thus, it cannot be conjunctively local of any order because if it were we can always create a figure larger where we can make it mess up and not notice its actually connected.

In addition as the authors mentioned at the end, connected can of course be computed if some predicate $\varphi\_i$ is allowed to see the whole 2D plane/image. However, this would be silly, since we need $k$ to be less than the size of the image, otherwise, we wouldn't really be constructing a meaningful definition for local. So we **must** have $k \< |image| = | R | $.

Btw, thanks Yuval!

---
Tags: algorithms, logic, artificial-intelligence, proof-assistants
---


# Question
Title: Is the exponent in floating point numbers signed or unsigned
This may be sound like a stupid question, because, of course, it can be negative and, as Wikipedia states:

> A numeric variable is signed if it can represent both positive and negative numbers, and unsigned if it can only represent non-negative numbers (zero or positive numbers).

But is it really? Because it doesn't work like normal signed integer, because doesn't really have a *sign*, it's just an unsigned integer starting at a negative point, it seems to me. I guess the first character *could indicate* whether it's negative xor positive / zero.

For people who don't remember CS class:

* exponent of -127: `0000 0000`
* exponent of zero: `0111 1111`
* exponent of one: `1000 0000`
* exponent of 128: `1111 1111`

# Answer
> 4 votes
This is mostly a matter of interpretation. For IEEE 754 floating point numbers (one of the most common implementations), an exponent bias is used:

> In IEEE 754 floating point numbers, the exponent is biased in the engineering sense of the word – the value stored is offset from the actual value by the exponent bias. Biasing is done because exponents have to be signed values in order to be able to represent both tiny and huge values, but two's complement, the usual representation for signed values, would make comparison harder.
>
> To solve this problem the exponent is biased before being stored, by adjusting its value to put it within an unsigned range suitable for comparison.

For floating point numbers with single-precision, the effective exponent has 8 bits and ranges from -126 to 127. However, the internal exponent ranges from 1 to 254, meaning that 127 has been added to the effective exponent. (This means it is valid to say that the exponents of floating point numbers are stored as unsigned integers, even though this is a matter of interpretation.)

In addition to the reasons outlined above, another good reason for this encoding is that two special exponents are required for floating point encoding according to IEEE 754: Floating point numbers can also store the values `Infinity`, `NaN` and denormalized values which would be too small to store them in the usual format.

The special constants used are the internal exponents $0$ and $2^r-1$ (where $r$ is the number of bits of the exponent), so in binary $0...0$ and $1...1$. These values are easy to recognize. Note that these exponents belong to effective exponents that are barely ever used. If we had used the internal exponent $0$ without shifting the range, it would be the same as the effective exponent $0$, making it difficult to encode common number ranges.

# Answer
> 0 votes
Whether a variable is signed or unsigned is a semantic feature. Floating point exponents are interpreted as signed numbers, so they are signed variables, irrespective of encoding details.

---
Tags: floating-point
---


# Question
Title: Error solving the next recurrence: $T(n)=7T(n/2)+n^2$
Hello I'm trying to solve this recurrence with the method that says the teacher that when you get to \begin{align\*} T\bigg(\frac{n}{2^{k}} \bigg) \end{align\*} you do \begin{align\*} \frac{n}{2^{k}} &= 1 \qquad (\text{by definition})\\ k &= \log\_{2}(n) \end{align\*}

\begin{align\*} T(n) &= 7T(n/2) + n^2 \\ &= 7^2T(n/2^2) + 7(n/2)^2 + n^2 \\ &= 7^3T(n/2^3) + 7^2(n/2^2)^2 + 7(n/2)^2 + n^2 \\ &=\cdots \\ &= 7^{k}T\bigg(\frac{n}{2^{k}}\bigg) + \sum\_{j=1}^{k-1} 7\frac{n}{2^{j}}+n^{2}\\ &= 7^{\log\_{2}(n)} + \sum\_{j=1}^{\log\_{2}(n)-1} 7\bigg(\frac{n}{2^{j}}\bigg)^{2}+n^{2}\\ \end{align\*}

After developing, I have left \begin{align\*} 7^{\log\_{2}(n)}+n^{2} \end{align\*} But I know the solution is \begin{align\*} n^{\log\_{2}(7)} \end{align\*}

What am I doing wrong?

# Answer
> 6 votes
Some of your sums have typos, but you already have the right answer.

Here's a useful fact about logarithms:

$a^{\lg b} = 2^{(\lg a) \cdot (\lg b)} = 2^{(\lg b) \cdot (\lg a)} = b^{\lg a}$

Apply it to your answer, keeping in mind that $\lg 7 \approx 2.8 \> 2$:

$O(7^{\lg n} + n^2) = O(n^{\lg 7} + n^2) = O(n^{\lg 7})$

# Answer
> 2 votes
There are indeed some typos as @Craig Gidney pointed out. Moreover you forgot the exponent for the '$7$' in the sum and the term $T(1)$...

I propose you the following solution (which is much similar to yours):

First of all let $n=2^k$ hence the initial recurrence turns into

$$T(2^k)=7\cdot T(2^{k-1})+4^k$$

Now setting $S(k)=T(2^k)$ we have

$$S(k)=7\cdot S(k-1)+4^k$$

Therefore we have

\begin{align\*} S(k)&=7\cdot S(k-1)+4^k\\ 7\cdot S(k-1)&=7^2\cdot S(k-2)+7\cdot 4^{k-1}\\ 7^2\cdot S(k-2)&=7^3\cdot S(k-3)+7^2\cdot 4^{k-2}\\ &\vdots\\ 7^{k-1}\cdot S(1)&=7^k\cdot S(0)+\sum\_{i=0}^{k-1}7^i4^{k-i} \end{align\*}

Summing-up we are left with

$$S(k)=7^k\cdot S(0)-\frac{4}{3}\cdot (4^k-7^k)$$

and substituting back the value of $n$ we have

$$T(n)=n^{\log\_2 7}\cdot T(1)-\frac{4}{3}(n^2-n^{\log\_2 7})$$

for $n\>0$.

Hope it helps.

# Answer
> 1 votes
Apparently the difference between $7^{log\_2(n)}$ and $n^{log\_2(7)}$ confused you (quite understandably). But take the base two logarithm on both sides:

$log\_2(a^b) = log\_2(a)·b$, so on the left side the logarithm is $log\_2(7)·log\_2(n)$, on the right side it is $log\_2(n)·log\_2(7)$. So both expressions are exactly the same.

---
Tags: algorithms, algorithm-analysis, recurrence-relation
---


# Question
Title: Support of a codeword in a binary linear code proof
Let $C$ be the binary linear code with the following generator matrix

$G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix}$

The *support of a codeword* is the set of coordinate positions in which the code word has nonzero entries. Let **$w$** $\in C$ be a code word of weight $4$. Show that there is no code word of weight $3$ in $C$ whose support is a subset of the support of **$w$**.

I think I have worked out that the codewords of weight $4$ in $C$ are: $\\{(1001011),(0010111),(0111001),(0101110),(1100101),(1110010),(1011100)\\}$ so does this mean that the support is $\\{(1,4,6,7),(3,5,6,7),(2,3,4,7)$ and so on..$\\}$? Then the codewords of weight $3$ are $\\{(1101000),(0110100),(0011010),(0001101),(1000110),(1010001),(010001)\\}$ ? with support of $\\{(1,2,4),(2,3,5),(3,4,5)$ and so on..$\\}$?

I'm not sure if this is right so far? But this is as far as I can get and do not know what to do next to show that there is no code word of weight $3$ in $C$ whose support is a subset of the support of **$w$**.

# Answer
If a codeword of weight 3 existed whose support was a subset of a codeword of weight 4, then you must have a codeword of weight 1 (since the difference of codewords is also a code word).

A codeword of weight 1 has one 1 and the rest zeros. Now, can you show that these don't exist?
> 1 votes

---
Tags: proof-techniques, coding-theory, error-correcting-codes
---


# Question
Title: Finding optimal sequence of questions to minimize total student time
Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \\{ q\_1 \ldots q\_k \\}$ and a set of $n$ students $S = \\{ s\_1 \ldots s\_n \\}$. Each student has a doubt in a certain subset of questions, i.e. for each student $s\_j$, let $Q\_j \subseteq Q$ be the set of questions that a student has a doubt it. Assume that $\forall 1 \leq j \leq n: Q\_j \neq \phi$ and $\bigcup\_{1\leq j\leq n}Q\_j = Q$.

All students enter the tutorial session in the beginning (at $t = 0$). Now, a student leaves the tutorial session as soon as all the questions in which he has a doubt in have been discussed. Suppose that the time taken to discuss each question is equal, say 1 unit$^\*$. Let $t\_j$ be the time spent by $s\_j$ in the tutorial session. We want to find out an optimal permutation $\sigma$ in which questions are discussed $(q\_{\sigma(1)} \ldots q\_{\sigma(n)})$ such the the quantity $T\_\sigma = \Sigma\_{1\leq j \leq n}t\_j$ is minimized.

I have not been able to design a polynomial time algorithm, or prove $\mathsf{NP}$-hardness.

We can define a decision version of the problem $$ \mathsf{TUT} = \\{\langle k, n, \mathcal{F}\_Q, C \rangle \mid \exists \sigma : T\_{\sigma} \leq C\\} $$

where $\mathcal{F}\_Q$ is the set of $Q\_j$'s.

We can then find out the minimum $T\_\sigma$ using binary search on $C$ and find out the optimal $\sigma$ using partial assignments to $\sigma$ in polynomial time using an oracle for $\mathsf{TUT}$. Also, $\mathsf{TUT} \in \mathsf{NP}$ because the optimal $\sigma$ can be used as a certificate which we can verify easily in polynomial time.

My question: Is $\mathsf{TUT}$ $\mathsf{NP}$-complete or can we design a polynomial time algorithm for it?

Sidenote: By the way, I thought of this question after an actual tutorial session, in which the TA discussed the questions in the normal order $q\_1 \ldots q\_n$ because of which many students had to wait until the end.

**Example**
Let $k=3$ and $n=2$. $Q\_1 = \\{q\_3\\}$ and $Q\_2 = \\{q\_1, q\_2, q\_3\\}$. We can see that an optimal $\sigma = \langle 3, 1, 2 \rangle$ because in that case, $s\_1$ leaves after $t\_1 = 1$ and $s\_2$ leaves after $t\_2 = 3$, so sum is 4.
However, if we discuss the questions in the order $\langle 1, 2, 3\rangle$, then $s\_1$ and $s\_2$ both have to wait till the end and $t\_1 = t\_2 = 3$, so sum is 6.

$^\*$You are free to solve the more general case where each question $q\_i$ takes $x\_i$ units to discuss!

# Answer
> 1 votes
I suspect the problem $\mathsf{TUT}$ to be NP-hard. I will show how to transform the problem such that it is strongly *related* to a problem which is NP-hard. (Yes, this is all rather vague. I basically think my general approach is correct, but I am currently unable to proceed.)

First, note that the problem $\mathsf{TUT}$ can be reformulated as follows:

Given a set of questions $Q$ of size $k$, a set of $n$ subsets $\mathcal{F}\_Q\subseteq \mathcal{P}(Q)$ and an integer $C$, does there exists a sequence $\Sigma : \langle S\_1,\ldots, S\_k\rangle$ such that, for all $i \in\\{1,\ldots,k\\}$:

1. $S\_i\subseteq Q$ and $|S\_i|=i$; and
2. $S\_i \subset S\_j$ for all $j\>i$; and
3. $\sum\_{i=1}^k |\\{q\in\mathcal{F}\_Q\mid q\not\subseteq S\_i\\}| \leq C$ ?

Note that the set $S\_i$ represent the first $i$ questions that will be explained. Conditions 1 and 2 ensure that the subsets are well formed according to this interpretation. Condition 3 counts the amount of students that haven't left at every moment in time, so it indeed sums up to the total waiting time among all students.

Now, we restrict the size of the subsets in $\mathcal{F}\_Q$ to $2$, so we can represent these subsets as edges on a graph where the vertices are the elements from $Q$. (A hardness result for this special case is sufficient for hardness of the general problem)

Now, the problem of minimizing $|\\{q\in\mathcal{F}\_Q\mid q\not\subseteq S\_i\\}|$ for a single $i$ (this is essentially ignoring condition 2) is equivalent to the following problem, which I dub '$\mathsf{\text{Double max $k$-vertex-cover}}$':

> Given an undirected graph $G=(V,E)$ and integers $k$ and $t$, does there exist a set of vertices $V'\subseteq V$ of size at most $k$ such that the set $\\{(u,v)\in E\mid u\in V' \wedge v \in V' \\}$ has a size of at least $t$?

This problem is NP-hard, since $k$-clique is a special case of this problem, as this answer shows. However, this is not sufficient to prove $\mathsf{TUT}$ to be NP-hard, since we need to find the maximum for every $i$, while respecting condition 2. This conditions are not satisfied by every sequence $\Sigma$ that satisfies only condition 1 and 3: consider the graph on $7$ vertices with two disjoint cycles, one of size $4$, the other size $3$. For $i=3$, selecting all vertices in the $3$-cycle gives the maximum, while selecting all vertices of the $4$-cycle is optimal for $i=4$.

It seems that condition 2 makes the problem even harder and most certainly not easier, which means $\mathsf{TUT}$ should be NP-hard, but I haven't seen a method to formally prove this.

So, to summarize, I have reduced the question to the following:

* Is it possible to include condition 2 to complete the hardness proof for $\mathsf{TUT}$?

---

Side note: The formulation I gave makes it tempting to try an iterative algorithm which finds $|\\{q\in\mathcal{F}\_Q\mid q\not\subseteq S\_i\\}|$ under condition 2 from $i=1\ldots k$, by finding all maximum 'extenstions' of all found maximum sets for $i-1$. This does not lead to an efficient algorithm, as the amount of maximum sets at a single iteration may be exponential in $k$. Additionally, I have not seen a method to determine whether a subset for some $i$ would eventually become the 'global' maximum to prevent checking an exponential amount of subsets.

---
Tags: algorithms, complexity-theory, np-complete, np-hard
---


title: What is a quotient structure?

text:
# Question
Title: What is a quotient structure?
I was reading a paper here, and it mentioned "quotient structure" in the following sentence (third page, second paragraph of the paper)

> In order to obtain a representation of terms truly isomorphic to λ-terms, we need to build a quotient structure, quotient the set of raw terms with respect to alpha-equivalence. This construction based on a quotient corresponds very closely to the of presentation from standard textbooks on λ-calculus.

I am hoping that someone could point me a good tutorial on quotient structures.

# Answer
> 6 votes
The idea is that two expressions which are α-equivalent are not meaningfully different. λx.λy.x and λz.λy.z are technically different expressions. They are α-equivalent, though, they intuitively represent the same thing. In most circumstances, differentiating between them is useless at best, counter-productive at most.

The quotient set is a formal definition that allows to say “we consider α-equivalent expressions to actually be the same”. So what is this formal definition?

### Equivalence relation

First of all, an **equivalence relation** ~ on a set *S* is a binary relation that is:

* reflexive: for every *x* in *S*, *x ~ x*.
* symmetric: for *x, y* in *S*, if *x ~ y*, then *y ~ x*.
* transitive: for *x, y, z* in *S*, if *x ~ y* and *y ~ z*, then *x ~ z*.

> Examples:
>
> * For any set, = is an equivalence relation.
> * *a = b* (mod *n*) is an equivalence relation.
> * α-equivalence is an equivalence relation.

### Equivalence class and quotient set

Now, given *S* and ~, and *a* in *S*, the **equivalence class** of *a* for ~ is the set \[*a*\] of all *x* in *S* such that *x ~ a*.

By reflexivity, it is clear that each *x* in *S* is in \[*x*\]. Moreover, using symmetry and transitivity, you can show that if *x* in \[*y*\], then \[*y*\] = \[*x*\]. So each *x* is in a single equivalence class, two distinct equivalence classes do not intersect.

Given *S* and ~, the set {\[*x*\] | *x* in *S*} of every equivalent class is a partition of S. This partition is called **quotient set** of *S* by ~ (usually noted *S*/~).

> Example: For the relation = (mod 5) on ***Z***, the equivalence classes are \[0\], \[1\], \[2\], \[3\], \[4\]. Each integer is equal to a single 0 ≤ *n* ≤ 4 modulo 5.

Usually, one doesn’t bother writing the \[ \] when it’s not necessary.

# Answer
> 5 votes
It's a term coming from abstract algebra. When you quotient a set $S$ with respect to some equivalence relation $\sim$, you are replacing the set $S$ with its equivalence classes under $\sim$. Often the set $S$ has operations defined on it, and in that case we want these operations to be well defined for the quotient $S/\sim$, in the sense that if $x\_i \sim y\_i$ then $x\_1 \circ x\_2 \sim y\_1 \circ y\_2$. This allows us to define $\circ$ on the quotient.

An example in real analysis is $L^p$ spaces, in which functions are defined "up to measure zero".

---
Tags: lambda-calculus, proof-assistants
---


# Question
Title: How to find the minimum number of states required by a DFA
Given a language $L = \left\\{ a^{nk+1} | n \> 0 \right\\}$ and $k$ is an integer constant.

How to show that a DFA for this language must have $k+2$ states or more states using minimum state lemma.

By minimum state lemma I mean the number of minimum state a DFA has is the number of pairewise distinguishable states. I have constructed a set of pairewise distinguishable string ${a, aa, aaa, ... a^{k+2}}$ with respect to L and found that I can not add anymore strings to it. But I don't know how to prove this string has the maximum number of pairewise distinguishable strings.

# Answer
> 0 votes
You can prove that your set is maximal in (at least) two different ways:

1. Show that every string is equivalent to one of the strings in your set.
2. Construct a DFA for the language having the same number of states as are strings in your set.

In your case both approaches are not too difficult.

Note, however, that the question only asks you to show that every DFA for the language must contain at least $k+2$ states. For this there is no need to show that your collection is maximal. If you find $k+2$ pairwise inequivalent strings, then it follows that every DFA for the language must contain at least $k+2$ states. If the collection is not maximal, all it means is that your bound isn't tight.

---
Tags: formal-languages, finite-automata
---


# Question
Title: Is 'double max-$k$ vertex-cover' NP-hard?
Consider the following problem, which I have called '$\mathsf{\text{double max $k$-vertex-cover}}$':

> Given an undirected graph $G=(V,E)$ and integers $k$ and $t$, does there exist a set of vertices $V'\subseteq V$ of size at most $k$ such that the set $\\{(u,v)\in E\mid u\in V' \wedge v \in V' \\}$ has a size of at least $t$?

Is this problem NP-hard?

I suspect it is, since the similar problem of max $k$-vertex cover is NP-hard. The same trick for that problem, setting $t=|E|$, does not apply here, as that gives the trivial answer of $|V|-\\#\text{zero-degree vertices}$ (in other words, double max vertex-cover is a trivial problem).

Unfortunately, I have been unable to find a reduction. This question seems related, but does not solve this problem for the same reason a reduction from minimum vertex cover fails. (A generalisation of this problem to set covering would look similar to that question)

---

Background: I encountered this problem in an attempt to show NP-hardness of another problem in this answer, but I think this problem is interesting on its own.

# Answer
> 5 votes
It was easier for me to show that the $k$-clique problem is a special case of this problem.

On an input graph $G$ and an integer $k$, the this special case is defined by $G$,$k$,$t$, with $t=\binom{k}{2}=k(k-1)/2$. Observe that some $V'\subseteq V$ of size $k$ is a clique in $G$ if and only if the set $V'$ covers at least $\binom{k}{2}$ edges twice.

Since the NP-hard problem $k$-clique is a special case of 'double max-$k$ vertex-cover', the problem 'double max-$k$ vertex-cover' is NP-hard.

---
Tags: algorithms, graphs, np-hard, set-cover
---


title: Algorithms for "mostly-SAT?"

text:
# Question
Title: Algorithms for "mostly-SAT?"
This is third-hand, so please bear with me. A collaborator was at a review meeting where he heard another participant make the claim that given an assignment for a SAT problem that satisfies (some high percentage) of clauses, there are polynomial time algorithms that finish the problem.

Is this true? Can someone point me to some references?

# Answer
This cannot be true, since you could use such an algorithm to solve SAT itself in polynomial time. Given a SAT instance $\varphi$, construct a much larger instance $\psi$ which contains $\varphi$ as well as many copies of the clause $x$, where $x$ is a new variable not appearing in $\varphi$. It is easy to find an assignment satisfying almost all clauses of $\psi$. Now run your algorithm. If it succeeds, then $\varphi$ is satisfiable; and moreover, if $\varphi$ is satisfiable then it should, indeed, succeed. Thus $\varphi$ is satisfiable iff your algorithm finds a satisfying assignment within the promised running time.

Perhaps the participant meant an assignment which is close to a satisfying assignment, as in Schöning's kSAT algorithm; see for example Eppstein's lecture notes.
> 1 votes

---
Tags: reference-request, satisfiability
---


title: Boolean absorption

text:
# Question
Title: Boolean absorption
> A and ( A or C ) = A

And

> A or A and C = A

How do these identities work?

Using the rule

> A and ( B or C ) = A and B or A and C

For the first identity, I get

> A and A or A and C = A or A and C

How is the C eliminated?

Mental substitution shows that it will equal A, but can it be algebraically shown.

Equation 2, too.

# Answer
> 17 votes
Here is one way to prove the first identity: $$ A \land (A \lor C) = (A \lor 0) \land (A \lor C) = A \lor (0 \land C) = A \lor 0 = A. $$ The second identity has a similar proof. Alternatively, you could use duality to deduce it from the first identity.

# Answer
> 6 votes
Here's one way of thinking how these identities "work". Of the first one, when *A* is false, *A and anything* is false; when *A* is true, *A or C* is true, and the whole thing is true too; therefore being equal *A* in both cases. Similarly, the second, when *A* is true, then *A or anything* is true; when *A* is false, *A and C* is false, and the whole expression is also false.

---
Tags: boolean-algebra
---


# Question
Title: Example of typed lambda term with recomputed argument
What is an example of a typed lambda term $\lambda x.\phi : A \to B$ and a term $a : A$ such that, when $\beta$-reducing the term $(\lambda x.\phi)(a)$, the argument $a$ must be repeated/recomputed several times?

# Answer
In the simply typed $\lambda$-calculus with pairs, a simple example is

$$(\lambda x :T. (x,x))a$$

where $a$ is a term of type $T$.
> 3 votes

---
Tags: lambda-calculus
---


title: Computing with number of stack items

text:
# Question
Title: Computing with number of stack items
For stack-oriented programming language, how many top-most items of the stack are needed to be accessible in order to be Turing complete?

Is it enough to be able to access just the top-most item? Two items? Three? Any item?

In the case of Forth, is it necessary to have `rot`, `pick`, `roll`? Why does `rot` operates with exactly top three items?

# Answer
It depends on what kinds of things you can store on the stack.

If each item on the stack is of unbounded size, you can simulate a two-counter machine, which is Turing-complete. Therefore, in this case, you can achieve Turing-completeness with just the ability to access the top two items on the stack.

If items are bounded-size, restricting to access a bounded number of top-most items of the stack gives something equivalent in power to a PDA. (For instance, suppose all you can do is access the top 5 items of the stack, and use that together with a finite control to transition to a new state of the finite control and either push/pop. Then grouping the items into 5-tuples, we can build an equivalent machine where you only need to access the topmost item. That machine is a PDA.) Therefore, in this case, it's not Turing complete with access to any finite number of items at the top of the stack.
> 2 votes

---
Tags: formal-languages, programming-languages, computation-models, stacks
---


# Question
Title: Given a prime power, is it possible to efficiently compute the prime
Suppose that I am given as input the number $p^i$ for some prime $p$ and some positive integer $i$. I wish to find $p$ and $i$.

Is there an algorithm to do this that works in time polynomial in the number of digits of $p^i$?

# Answer
> 5 votes
Yes, here is a simple approach (there are likely more efficient ones).

Let $n$ be the number given. Observe that $2 \leq p \leq n$ and $1 \leq i \leq \log\_2(n)$. For each possible value of $i$ in the range $\\{1, \ldots, \log\_2(n)\\}$, you can do a binary search for a $p$ in the range $\\{2, \ldots, n\\}$ such that $p^{i} = n$.

---
Tags: algorithms, primes
---