# Question
Title: Randomly generated binary search trees case comparison
Although not an assignment, just out of curiosity; I am trying to compare a two cases

1. A scenario where I pick a tree out of the set of possible binary search trees on the keys $1,2,\ldots,n$, with each tree equally likely (with a probability say, $p(T)$) and\
2. Generating a binary search tree by inserting the numbers $1,2,\ldots,n$ in random order with a probability, $q(T)$ of obtaining the tree $T$ in this way.

I can infer that $p(T)$ would not be necessarily equal to $q(T)$ but I can't seem to explain why. An example would help.

# Answer
1. Any tree structure of size $n$ is a possible structure for a binary search tree on $\\{1, …, n\\}$. Since there are $C\_n = \frac{1}{n+1}\binom{2n}{n}$ such trees (see Catalan numbers), if $T$ is a BST, we get $p(T) = p\_n=\frac{n+1}{\binom{2n}{n}}$. For example, $p\_3 = \frac1{5}$.
2. There are $5$ BST of size $3$, but $6$ permutations. That means that two of those permutations create the same BST. Indeed, $(2, 1, 3)$ and $(2, 3, 1)$ create the same tree $T$ such that $q(T) = 2\frac16 = \frac13$. For all other trees, $q(T) = \frac16$.
> 2 votes

---
Tags: binary-trees, search-trees, binary-search-trees
---


# Question
Title: Does contradiction definitively prove nonexistence
It is common to have proofs that use contradiction to show that some language is undecidable in computability theory.

An example proof can be seen in 4.2 Undecidability “Introduction to the Theory of Computation” by Sipser proving 4.11 the undecidability of A\_tm.

Basically, these proofs assume the existence of a decider for the undecidable language in question. They then find a contradiction due to their existence.

What I would like to better understand is how does a contradiction prove nonexistence? Couldn’t it instead be the case that the whole model of computability is flawed in a way that it allows for contradictions?

Basically, it seems to me that assuming some decider exists and arriving at a contradiction shows either:

1. the decider cannot exist OR
2. the model of computation is flawed in a way that there can be deciders that cause logical contradictions

Wouldn’t this be somewhat related to Godel’s incompleteness concepts?

# Answer
> 20 votes
A proof is a proof, even if the system you work in is inconsistent.

So if you prove that the existence of a decider leads to contradiction, you have proved that such a decider does not exist. If in addition your system is contradictory, then it will also prove that the decider exists, as well as that you are the Pope. But your proof of non-existence will remain valid. You might want to change the system, though.

# Answer
> 6 votes
That's not how I would describe it. I would say, the proof proves that such a decider cannot exist.

I know that many people find proof by contradiction unconvincing or it makes them uncomfortable, and they wonder whether one can really trust the results one obtain via such proofs. The undecidability results you're likely to run into can typically also be proved, without using proof by contradiction (and in my experience it typically is quite easy to transform the proofs accordingly). So, one can go through the straightforward exercise of converting that proof into one that doesn't use proof by contradiction. I suggest you ask yourself, as a thought experiment, whether you would have the same reaction if you were shown a proof of the result that didn't use proof by contradiction.

Suppose I show you a theorem that $\sqrt{2}$ is irrational. Do you conclude that there does not exist any rational fraction $p/q$ such that $(p/q)^2=2$? Or, do you conclude that either such a fraction does not exist, or else mathematics is flawed in such a way that makes such theorems untrustworthy? I suppose in some sense both conclusions are valid, but normally we trust in mathematics and go with the former conclusion. The same applies this situation here. There is nothing special about these undecidability proofs that requires adding some extra "or else math is flawed" clause.

Of course, if there is a logical contradiction in math, then you can prove everything: you can prove that $1+1=2$, that $1+1=3$, that $\sqrt{2}$ is irrational, that $\sqrt{2}$ is rational, that there is no decider for an undecidable problem, that there is a decider for an undecidable problem. In particular, it is reasonable to conclude that there is no decider for the problem (even if there is a logical contradiction in math, then that implies there is no decider for the problem, by the prior remarks).

# Answer
> 5 votes
# Implication

All of science is built on the principle of implication: truth can only imply truth. It cannot imply falsehood. False can imply anything, therefore you cannot rely upon it to derive truth. By starting with a set of truths, one can derive more truths without a falsehood sneaking in. This is logically necessary. If your system of reasoning does not provide this guarantee, then you have no system of reasoning at all, and no reliable way to derive new truths. You might as well resort to crystal balls and magic lamps.

If you derive a contradiction in a chain of reasoning, and the steps in the chain are all proper implications, then the starting premise cannot be true, because a contradiction is exactly the statement: T -\> F (true implies false). The entire system of constructing proofs is a framework for ensuring that each step is indeed a proper implication that preserves the "truthiness" of the original premise. Thus, when you arrive at a step in which you imply false, you can collapse the chain of implications backwards by saying: "Therefore, step 9's premise is false. Since step 8 implies step 9, step 8's premise is false. Since step 7 implies step 8, step 7's premise is false." All the way back to: "Therefore, my starting premise is false."

If this entire mechanism has a hole in it, one that allows truth to derive false, then you have not discovered a powerful new truth: you have destroyed the very system that allows you to systematically derive truth to begin with. You have essentially destroyed your very ability to conduct science and mathematics at all.

If you wish to make any kind of scientific statement at all, via experimental or logical proofs, you need to have a system of logic which implements implication to begin with. And once you have material implication, you have non-contradiction and proof by contradiction as inevitable consequences of that. If you somehow lose proof by contradiction, then you also lose implication, and you now must find some other way to arrive at truth. But don't claim that your new system is based on logic, because it's not.

# Sudoku

It might help to think of proofs like a sudoku puzzle. If you reach a point where the number 3 appears twice in the same row, you have a problem: you either made a mistake in your deductions, or you don't have a valid sudoku puzzle. What you cannot say is: "My deductions are all valid, this puzzle is a valid sudoku, and there are multiple 3s in this column. I have discovered that sudoku admits this possibility." It does not. The very definition of sudoku prevents this possibility. At no point will you have discovered that sudoku is flawed in a way that allows duplicate numbers.

That's because the definition of sudoku does not allow it. If you have a grid with duplicates, then it's not a sudoku puzzle. It's just a grid with numbers. And if you have a proof that leads to a contradiction, you don't have evidence that mathematics is broken, because the premise is true after all. What you have is a broken proof or a broken premise.

# Goedel's Theorems

You are suggesting that Goedel's Incompleteness Theorems will save you by saying: "I proved that P leads to a contradiction, but Goedel tells me that P is really true after all!" That is not what the theorems say. They say that a sufficiently complex proof system is either incomplete or inconsistent. If it's inconsistent, then it's useless: you can prove T -\> F, and thus you can prove any statement you like in it. You cannot use an inconsistent system to discover actual truth. Therefore, scientists and mathematicians choose to work in incomplete systems, with the consequence that some statements will be true, but you will not be able to prove they are true within that system (but you can by creating a larger system that contains it).

An undecidable statement is one in which assuming it true does not lead to a contradiction, but assuming it false also does not lead to a contradiction. And thus, the rules of the formal system are unable to determine whether the statement is true or false. On the other hand, if a statement derives false, then in that formal system, the statement is false, full stop.

There is clearly an asymmetry between truth and falsehood and how they propagate and what you can learn from them. And this is why these results can sometimes be confusing. But it is also why they are so powerful: truth is more restrictive than falsehood, which is why it is so difficult to maintain a web of lies. You only need one contradiction to see that the web is a fabrication. Truth networks need no self-consistency effort, because it is an intrinsic property of truth itself.

# Conclusion

Systematically discovering truth works because material implication is a "truth-preserving" operation. Once you derive false (i.e., a contradiction), you can propagate that all the way back to the starting premise. If this process is not valid, then your entire system of procedure is also not valid, and you do not have a reliable system for discovering truth.

# Answer
> 2 votes
The whole idea of the ad-absurdum proofs is that the world we prove something in is based on logic and is logically consistent. This is kind of an axiom (a given).

If you now show that some assumption leads to a contradiction, you show that either one is true:

* The assumption is false.
* The way you use to show “assumption ⇒ contradiction” is flawed.
* The world in which you show this is not logically consistent.

But the last point is so disruptive that it also moots all the logical conclusions we can draw here, so it isn’t really worth examining. At least not in a logical discussion; it might make sense in a philosophical discussion.

That leaves two possible culprits: Either the assumption is wrong or the proof is flawed. If you can rule out the latter (by working thoroughly, having a proper peer-review, etc.), the assumption must be wrong.

So, yes, if something leads to a contradiction, it means it cannot be true in a logically consistent world. If your assumption was the existence of something, that something doesn’t exist.

# Answer
> 1 votes
Another way to look at it is, by reaching a contradiction you've shown that one of your assumptions is incorrect. This is usually the assumption stated at the start of the proof, but it could also be another, unstated assumption. *"The system I'm working in is inconsistent"* is one possibility *(albeit unlikely)*.

This isn't just theoretical. It's actually fairly common for a proof to be submitted, only for a reviewer to find a hidden assumption in the proof. In rare cases this can be so subtle that it takes years or even decades to find.

---
Tags: undecidability, proof-techniques
---


title: How to resolv this NAT problem?

text:
# Question
Title: How to resolv this NAT problem?
I am taking my first network class and I came across a question I just cant wrap my head around.

We have an external machine that has a public IP address from using NAT, the external machine want to contact one other machines but using their local IP address no the one public provided by NAT. How can initiate the connection in order for the remote machine to contact the local one?

How to know which machine the remote machine will connect to?

Any tips would be highly appreciated

# Answer
I understand your question the following way:

> There are multiple computers behind a NAT. The NAT has a global IP address while the computers behind the NAT only have a local IP address.
>
> A computer in the Internet wants to send some data to a computer behind the NAT.
>
> How is this possible?

First of all:

The NAT needs to know which computer should receive a certain IP packet.

Using *real* NATs, this is typically only possible using **Port Forwarding**:

The NAT does not only evaluate the IP addresses of the incoming packet, but also the TCP port numbers (in the case of a TCP connection).

Depending on the TCP port number, the NAT will send the IP packet to one computer or another one. Example: If the port number is 443, the NAT will send the packet to the web server, if the port number is 25, it will send the packet to the e-mail server.

The person who operates the NAT must configure it in a way that the NAT knows which port number shall be sent to which local IP address.

If that person does not configure the NAT, the NAT does not know which packets shall be sent to which computer and it is **not possible** to send data to computers behind the NAT.

(By the way:

This is one of the reasons why there are a lot of people who plan to continue using "IPv4-like" NAT together with the new IPv6 protocol, which does not require NAT any more:

They argue that using NAT it is not possible for a hacker to send unwanted data to a computer behind the NAT.)

*Theoretically* it would also be possible to build a NAT that accepts "proxy server" connections at a certain TCP port (8080 is often used for proxy servers).

This would work the following way:

```
Computer in                      10.2.3.4
the Internet           NAT       TCP port 1234
     |                  |              |
     |----------------->|              |
     |  (connect to     |              |
     |  TCP port 8080)  |              |
     |                  |              |
     |----------------->|              |
     | Send data:       |              |
     | "10.2.3.4:1234"  |------------->|
     |                  | (connect)    |
     |<-----------------|              |
     | Send data:       |              |
     | "SUCCESS"        |              |
     |                  |              |
     |----------------->|              |
     | Send data:       |------------->|
     | "hello"          | Send data:   |
     |                  | "hello"      |
     |                  |              |
     |                  |<-------------|
     |<-----------------| Send data:   |
     | Send data:       | "world"      |
     | "world"          |              |
              ...

```
> 1 votes

---
Tags: computer-networks, security
---


title: Choices in cpu-scheduling decisions

text:
# Question
Title: Choices in cpu-scheduling decisions
I'm reading Operating System Concepts by Silberschatz and in chapter 5, there is this text:
1.

> CPU-scheduling decisions may take place under the following four circumstances:
>
> 1. When a process switches from the running state to the waiting state (for example, as the result of an I/O request or an invocation of wait() for the termination of a child process)
> 2. When a process switches from the running state to the ready state (for example, when an interrupt occurs)
> 3. When a process switches from the waiting state to the ready state (for example, at completion of I/O)
> 4. When a process terminates
>
> For situations 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for execution. There is a choice, however, for situations 2 and 3.

What does the author mean by choice? Does he mean that in situations 2 and 3, a new process might not be selected for execution when a process switches from the running to the ready state or from waiting to the ready state? Does that mean the CPU becomes idle? Is it preemptive scheduling?

2.

> When scheduling takes place only under circumstances 1 and 4, we say that the scheduling scheme is nonpreemptive or cooperative. Otherwise, it is preemptive. \[...\]Windows 95 introduced preemptivescheduling, and all subsequent versions of Windows operating systems have used preemptive scheduling. The Mac OS X operating system for the Macintosh also uses preemptive scheduling; previous versions of the Macintosh operating system relied on cooperative scheduling.

Does it mean that both newer versions of Windows and Mac OS X do not support situations 1 and 4 above as they are preemptive?

# Answer
This post answers major part of your question.

> Does that mean the CPU becomes idle?

It can, but the chances are extremely slim. The goal of scheduling is to maximise cpu utilization, in modern operating systems, the cpu is almost never "idle"(different from idle). However for arguments sake, the cpu can be considered to be idle when all processes are waiting or there is no process to run.

> Does it mean that both newer versions of Windows and Mac OS X do not support situations 1 and 4 above as they are preemptive?

No. The situations merely describe whether the scheduling decision is taken preemptively or non-preemptively. They are not dictating the behavior of the process or scheduling algorithm. In any system all the situations can arise and they all need to be handled by respective schedulers.
> 1 votes

# Answer
Q1. Choice means that there are several candidate processes that could be wakened. So some arbitration rule must exist.

Q2. No, situations 1 and 4 do arise all the time and it is obviously out of question not to "support" them.

Non-preemptive schemes are poor because they let processes monopolize the processor. They are not used anymore.

Interestingly, preemptive OSes existed long before microcomputers, on mainframes and minicomputers, but their adoption by the former took many years.
> 1 votes

# Answer
In condition 1 : CPU can execute only either the child() or wait() which ever is invoked . For 2 and 3 , during an interrupt generally CPU can either serve the interrupt while keeping the current process on postponed ( or wait ) or can continue with current process and later serve the interrupt. in 4 , CPU has no option other than to pick a new process, as the current one is done.

(couldn't comment , less points)
> 0 votes

---
Tags: operating-systems, scheduling
---


# Question
Title: Simple Uniform hashing with chances of no collision
I know that if I have $n$ different values in an array of size $m$ (where $m\>n$) under simple uniform hashing, the average probability of the total number of collisions is: $$\sum\_{i=1}^{n-1}\frac{i}{m}=\frac{n(n-1)}{2m}$$

Since it is known that the probability of no collision is $$1\cdot\left(1-\frac{1}{m}\right)\cdot\left(1-\frac{2}{m}\right)\cdots\left(1-\frac{n-1}{m}\right)$$ My question is $\textbf{how to prove}$ that the chances of no collision is $\textbf{at most}$ $\left(1-\frac{n-1}{2m}\right)^n$(viewing it as an the upper bound)

# Answer
You want to prove the following: $$\prod\limits\_{i=0}^{n-1}\left(1-\frac{i}m\right)\leqslant \left(1-\frac{n-1}{2m}\right)^n$$

One way to prove it is to prove: $$\left(1-\frac{i}m\right)\left(1-\frac{n-1-i}m\right)\leqslant\left(1-\frac{n-1}{2m}\right)^2$$ for all $i\in \\{1, …, \left\lfloor\frac{n-1}2\right\rfloor\\}$. This is quite feasible, it follows from the fact that the function $x\mapsto x(n-1-x)$ reach its maximum in $x=\frac{n-1}2$.
> 0 votes

---
Tags: hash, hash-tables, hashing
---


title: About a ℙ≠ℕℙ proof

text:
# Question
Title: About a ℙ≠ℕℙ proof
**Executable:** Sat *prog*
**Definition:** The exit status of "Sat *prog*" is 1 iff there exists an instance
*prog arg* which runs in P-time and the exit status is 1.
From the definition, Sat computes a ℕℙ problem.
If ℕℙ=ℙ, then, an executable f exists that "Sat f" should run in P-time:
// C source of executable f
#include \<stdlib.h\>
int main(int, char\* \[\]) {
return system("Sat f")? 0:1;
}
**Brief analysis:**
If Sat(f)==1, from definition of f, f(\*)==0. But, from definition of Sat, ∃x,f(x)==1 ... Contradiction
If Sat(f)==0, from definition of f, f(\*)==1. But, from definition of Sat, ∀x,f(x)==0 ... Contradiction (Exact negation should read: For all *prog arg* instance, *prog arg* does not run in P-time or the exit status of *prog arg* is not 1).
**Conclusion:** If ℙ=ℕℙ, there exists instances like f that Sat cannot decide. Therefore, ℙ≠ℕℙ.

----------------------
**Answer to possible questions:**

1. Given a polynomial formula P(x). We measure the execution steps t of an executable f (or function f(x)). If t\<=P(|f|+|x|), we say f(x) runs in P-times. Note that the definition of Sat (and ℕℙ) does not require *prog* be a "P-time executable". *prog* can actually never terminate. In this case, the exit staus of "Sat *prog*" is 0.
2. Sat is not shown undecidable, because the provided example f is only valid when "Sat *prog*" is assumed to compute in P-time.

I am not familiar with complexity theory. Such proof does not look like a traditional theoretical proof
(would be many pages). Nonetheless, it is thought a valid proof, because the argument is supported by 'real programs', what can go wrong?

# Answer
> 6 votes
What you showed is that no such program "Sat" can exist. Note that the complexity didn't matter here, since the argument still holds valid for any other complexity classes (a sign of this is that the analysis does not make a reference to the complexity of "Sat").

In fact, this is a well known fact! One can reduce the halting problem to the description of the problem that your "Sat" claims to solve, and since there is no turing machine (i.e, program) that solves the halting problem (and also always halts) - there also won't be one for this.

# Answer
> 3 votes
You seem to be confused about what it means for a program to run in polynomial time. It expresses a relationship between the size of the input offered to the program and its execution time on that input, namely, that that time is bounded by a polynomial in the input size.

> The exit status of "Sat prog" is 1 iff there exists an instance *prog arg* which runs in P-time and the exit status is 1.

It does not make any sense to say that *prog arg* "runs in P-time". The time it takes *prog* to run on *arg* is just a number, it is not a function. What you need to look at is the relationship between the time it takes *prog* to run on any possible *arg* and the size of those *arg*s.

> From the definition, *Sat* computes a ℕℙ problem.

It doesn't. *Sat* computes an uncomputable problem, which is why it can't exist (see nir sharar's answer). Your definition of *Sat* has nothing to do with ℕℙ or with satisfiability of Boolean formulas. What relationship do you see?

---
Tags: np-complete, complexity-classes
---


# Question
Title: Why the Following Grammars Are Not in CNF
I am reading the book "Automata, Formal Languages, and Automata" written by Dr. Emre Sermutlu and in page 153, it is stated that the following grammars are not in Chomsky Normal Definition (CNF):

> $G\_1$ :
> $S\rightarrow TT\mid a$
> $T\rightarrow ST \mid b$
>
> $G\_2$ :
> $S \rightarrow TT \mid a$
> $T \rightarrow a \mid b \mid \varepsilon$

The definition of Chomsky Normal Form is defined here: (https://en.wikipedia.org/wiki/Chomsky\_normal\_form). Why G1 and G2 are not CNF?

# Answer
> 2 votes
For the first one, the transition $T\rightarrow ST$ is not allowed, because in a transition $A\rightarrow BC$, neither $B$ nor $C$ must be the start symbol.

For the second one, the transition $T\rightarrow \varepsilon$ is not allowed, because only the start symbol ($S$) can be replaced with $\varepsilon$.

---
Tags: context-free, formal-grammars, normal-forms
---


title: How would one reduce HaltTM to ATM

text:
# Question
Title: How would one reduce HaltTM to ATM
Assuming that ATM is decidable, how to build a TM S that uses a TM R that takes as input and decides if M accepts w, to decide HaltTM, which we already know is undecidable, hence ATM isn't decidable. So how exactly do we go about this?

# Answer
For the sake of argument we will assume $A\_{TM}$ is decidable. Now we are going to show a way to decide $HALT\_{TM}$ using a decider for $A\_{TM}$ and thus reach a contradiction, since we know $HALT\_{TM}$ is undecidable.

Details:

If $A\_{TM}$ is decidable, then its complement $\overline{A\_{TM}}$ is also decidable. Suppose TM $R$ decides $A\_{TM}$ and $S$ decides $\overline{A\_{TM}}$. We use those to build TM $X$ that takes input $\left\<M, w\right\>$, a TM description $M$ and input $w$.

1. Run $R$ on $\left\<M, w\right\>$.
2. If $R$ accepts, then $X$ accepts.
3. If $R$ rejects, then run $S$ on $\left\<M, w\right\>$.
4. If $S$ accepts, then $X$ accepts.
5. If $S$ rejects, then $X$ rejects.

Thus, $X$ will reject only machines that do not halt and will accept all others. So we have used a decider for $A\_{TM}$ to construct a decider for $HALT\_{TM}$. But $HALT\_{TM}$ is undecidable, so we conclude that $A\_{TM}$ is undecidable.
> 2 votes

# Answer
Let R be a TM that decides ATM.

Build a new machine G =

```
"On input x:

For i = 1,2,...

Simulate M for i steps.

If M halted before the i'th step, accept.

Otherwise, continue to next i iteration."

```

Now run R on input (G,42). if R accets, accept. if R rejects, reject.

Note 42 is arbirtary (G completely ignores input x anyway).

Explanation: This R will accept iff G accepts, but G accepts iff M halts on w after some i steps.
> 0 votes

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


# Question
Title: How can it be formally proved that $f \in O(⌊f ⌋)$
I'm trying to prove that $f \in \mathcal{O}(\lfloor f \rfloor)$ given that $\forall m \in \mathbb{N}, f(m) \geq 1$

Here's what I've thought of so far, we can set C = 10 and k = 1 and somehow prove that this would eventually dominate the function? Not sure how I can prove this without a concrete function defined for $f$

According to the definition of big O,

For any C larger than 1, C times floor of f would eventually dominate f. What I can't figure out is how to outline this in a formal proof. Any help is appreciated!

# Answer
$$\\{f\\}\<1\le\lfloor f\rfloor\implies f=\lfloor f\rfloor+\\{f\\}\<2\lfloor f\rfloor.$$

---

Together with $2\lfloor f\rfloor\le2f$, that makes $f=\Theta(\lfloor f\rfloor)$.
> 1 votes

---
Tags: runtime-analysis, proof-techniques, big-o-notation
---


# Question
Title: How many bits are needed to reference physical vs virtual addresses?
I trying to learn about virtual memory at the moment and one of the explanations I've look at has a diagram like below. You can see that 32 bit virtual addresses are used so the virtual address space is 2^32 addresses and the computer must have RAM of a capacity 4GiB or smaller. You can see the physical addresses in the diagram are only represented with 30 bits though so 1GiB of physical memory is present which is where my confusion is. I though there must be 32-bits physical addresses as well because there are also 2^32 physical addresses and that the hard disk is used to store the physical pages that won't fit in main memory. Am I missing something?

# Answer
> 1 votes
Intel built 32 bit chips a while ago that could access more than 4 GByte of RAM.

You have two addresses for data: You have a logical address that your software cares about, and you may have a physical address with actual RAM (or video memory, or hardware that can be controlled with memory read/write instructions).

If you run more than one process, each process can use the same logical addresses, but they refer to different actual data. So with these older memory chips, process one could have 0 to 4GB logical space mapped to RAM at location 1GB to 5GB, process two could have 0 to 4GB logical space mapped to RAM at location 5GB to 9GB, and no RAM with addresses 0 to 1GB at all.

On the other hand, the latest processors have 64 bits for logical addresses (that's 256 billion billion bytes) and only 53 bits for physical addresses (which is about 8 million billion bytes, which is just a little bit more than I can afford. I can order a computer with 1500 billion bytes of RAM on the internet for 20,000 to 30,000 dollars, so 41 bits wouldn't have been enough).

Your example seems to only have 30 bits for physical addresses, so it is limited to one billion bytes. Unless some different tricks are involved, which are not needed nowadays.

# Answer
> 1 votes
A key benefit of virtual memory is a complete decoupling between the virtual address space and the physical locations. The virtual memory manager maps the virtual addresses of a process to some physical space that can reside on disk or in RAM (as pages), and that mapping changes dynamically. The RAM space of the machine can and is often smaller than the virtual space (in theory, a computer could work with a single page of RAM). It could also be larger !

It is also important to understand that all processes enjoy the same virtual space free for their own use, regardless the coexistence of other processes. The memory manager maps independently for every process.

In fact, a modern OS simulates several computers with a large RAM space, each assigned to a process, in a transparent way.

---
Tags: computer-architecture, memory-management, memory-hardware, virtual-memory, paging
---


title: Chord Ring with limited table size of 3

text:
# Question
Title: Chord Ring with limited table size of 3
In the normal case of a chord ring the big O notation of the look up is O(logn) because of long haul pointers of the Finger Table (or Routing Table).

In this question what if the Finger Table has a limit of size 3

(1) I would like to ask the Big O notation of the look up AND (2) I would like to know the formula for the 1st, 2nd and 3rd Index of a Finger Table.

# Answer
> 0 votes
O(log(N^2/3))

Because you will divide the chord into 3 equal parts and so does every node's neighbour.

Thus, Maximally you will go through 2/3's of the chord for each node.

Draw 2-3 nodes on a circular diagram and it will be easier to understand.

# Answer
> 0 votes
You haven't specified what entries are put in the finger table. The answer depends on that, so the question is not answerable. A lookup might take as many as $O(N)$ steps if you choose the finger table poorly (e.g., you select the next 3 nodes in the circle), or might take as few as $O(N^{1/4})$ steps if you choose the finger table well (e.g., you select the nodes at distance $N^{1/4}$, $N^{1/2}$, and $N^{3/4}$).

---
Tags: algorithms, distributed-systems, hash-tables, peer-to-peer
---


# Question
Title: Can we apply the Master Theorem to the following recurrence?
Our recurrence is

$$ T(n)= \begin{cases} T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if $n\>1$} \\ 1 & \text{if $n=1.$} \end{cases} $$

I have identified $a = 1 \> 0$, and $b = 2 \> 1$. I am having trouble identifying the $c$ (for $n^{c}$ in $f(n) =(\log(n))^{2}$. The best I could break it down to was $(\log(n))^{2} = \log(n)^{1}\*\log(n)^{1}$, which doesn't seem to be the form we are looking for, as $\log(n) \ne n$. Also, how do we take the floor operator into account?

If it follows that we can't apply the Master Theorem (which seems to be the case), what is the culprit?

# Answer
So, we have that $f(n) = O(n^c \log^k(n)) = O(n^0 \log^2(n))$; and since $log\_b(a) = log\_2(1) = 0 = c$, we are in the 2nd case of the Master's theorem (work to divide the problems is comparable to the work on subproblems (wiki)); thus, applying the theorem, we get $T(n) = \Theta(log^3(n))$.

On the floor operation, I don't know what is the cleanest way of solving it; one way could be to prove it for $n = 2^m$, and then extend to all $\mathbf{N}$ by monotonicity.

We can also calculate $T(n)$ directly:

$$T(n) = T(n/2) + log^2(n) = \sum\_{j=0}^{log(n)} log^2(2^j) = log^2(2) \sum\_{j = 0}^{log(n)} j^2 = \theta(log^3(n))$$
> 1 votes

# Answer
Let $S(n) := T(2^n)$, then $S(0) = 1$ and $S(n) = S(n-1) + n^2$ for $n ≥ 1$. $S(n)$ is therefore just a straightforward sum, $1 + sum(n'^2)$ for $1 ≤ n' ≤ n$, roughly $n^3 / 3$.

So $T(n)$ = roughly $(\log n)^3 / 3$ if n is a power of two, you can find the exact value. If n is not a power of two then $T(n^k) ≤ T(n) ≤ T(2 \cdot 2^k)$ for two powers of two around n. You can get it a bit more precise: If you calculate $T(c \cdot 2^k)$ for $1 ≤ c ≤ 2$, then you will repeatedly have $(\log c + n')^2$ instead of $(n')^2$. Your sum will be about $T(c \cdot 2^k) ≈ \log c \cdot k + (\log k)^3 / 3$ which will be about $(\log n)^3$ for $n = c \cdot 2^k$. (Obviously find a more precise formula for the sum of n^2).
> 0 votes

---
Tags: algorithms, asymptotics, master-theorem, divide-and-conquer
---


# Question
Title: Intuition of Flod-Warshall shortest path algorithm
I try to wrap my head around the Floyd-Warshall algorithm, and I don't understand why the shortest path is guaranteed to be found since we check only the alternative connections up to one hop deep.

For example, let's consider the following graph with four vertices:

```
    A  B  C  D
  A 0  5 -1  x
  B x  x  x  x
  C x  x  x -1
  D x  3  x  x

```

The shortest path from A to B is A -\> C -\> D -\> B and its weight is 1. However, AB is the first pair of vertices that are considered, so the connection C -\> B is not yet in the table and the shortest distance is not relaxed from 5 to 1.

Am I missing something?

# Answer
(Kleene-Roy-)Floyd-Warshall(-Ingerman)'s algorithm is defined iteratively, progressively increasing the number of allowed intermediate vertices.

1. at the first step, no vertex is allowed as an intermediate. Since $(A, B)$ is an edge, $w(A, B) = 5$ is considered the minimum possible weight. Overall, the matrix of distances is the same as the weighted adjacency matrix: $$\begin{pmatrix}0&5&-1&\infty\\\infty&\infty&\infty&\infty\\\infty&\infty&\infty&-1\\\infty&3&\infty&\infty\end{pmatrix}$$
2. at the second step, only vertex $A$ is allowed as an intermediate. The path $(A, A, B)$ is considered, but since $w(A, A) + w(A, B) = w(A, B)$, no modification is done. No other change is done to the matrix.
3. at the third step, only $\\{A, B\\}$ are allowed as intermediates. No change is done to the matrix.
4. at the fourth step, only $\\{A, B, C\\}$ are allowed as intermediates. There is now a possible path from $A$ to $D$: $$\begin{pmatrix}0&5&-1&-2\\\infty&\infty&\infty&\infty\\\infty&\infty&\infty&-1\\\infty&3&\infty&\infty\end{pmatrix}$$
5. at the fifth and last step, all vertices are allowed as intermediates. Two changes result from that: there is now a path considered from $C$ to $B$, and there is a new path considered from $A$ to $B$, with lesser weight than the previous one. The matrix is updated: $$\begin{pmatrix}0&1&-1&-2\\\infty&\infty&\infty&\infty\\\infty&-4&\infty&-1\\\infty&3&\infty&\infty\end{pmatrix}$$

The idea with this dynamic programming algorithm is that a path from $s$ to $t$ using no other vertex than the $k$ first vertices as intermediates can be one of the two:

* a path from $s$ to $t$ using no other vertex than the $k - 1$ first vertices as intermediates;
* a path from $s$ to the $k$-th vertex followed by a path from the $k$-th vertex to $t$, both parts using no other vertex than the $k-1$ first vertices as intermidates.
> 1 votes

---
Tags: graphs, shortest-path
---


# Question
Title: Choose non-adjacent numbers from intervals
Given a list of intervals with integral endpoints, we want to find out if we can choose one integer from each interval so that no two chosen numbers are adjacent. Can we do this in polynomial time?

My attempt is the following greedy strategy: Sort the intervals by the smaller left endpoint, breaking ties by the smaller right endpoint. Then, as long as possible, choose the leftmost feasible number from each interval.

However, this doesn't work: the first interval may be $\[5,9\]$ and the second interval $\[6,6\]$. Choosing $5$ from the first interval rules out choosing anything from the second interval. It would be better to choose $6$ from the second interval and $8$ from the first interval.

# Answer
> 3 votes
This problem can be regarded as a scheduling problem.

Each interval corresponds to a job. For each interval $\[L\_i,R\_i\]$, Let $r\_i = L\_i$ be the release time, $d\_i = R\_i + 2$ be the deadline, and $p\_i = 2$ be the job length. Then, single-machine no-preemption scheduling corresponds to a solution. Scheduling with non-integer start times can be converted to integer start times by taking the floor function, and the schedule remains feasible.

This problem has an $O(n \log n)$-time solution \[1\].

* \[1\] Garey, Michael R., et al. "Scheduling unit–time tasks with arbitrary release times and deadlines." SIAM Journal on Computing (1981).

# Answer
> 1 votes
I had an idea for a polynomial time algorithm, but here is a counter-example. I leave it visible for the sake of having an interesting input instance. I thought that the decisions didn't propagate too far, but that's clearly not true.

$I = \\{ \[1,8\], \[2,3\], \[3,5\], \[5,6\] \\}$. The solution is $\\{2,4,6,8\\}$.

Invalid solution

```
 1  2  3  4  5  6  7  8
[·                     ]
   [   ·]
      [      ·]
            [    ]

```

Valid solution

```
 1  2  3  4  5  6  7  8
[                     ·]
   [·   ]
      [   ·   ]
            [   ·]

```

---

I'm reminded of Hall's theorem here. You could say that for it to be a yes instance, every subset of intervals $S$ need to have $\text{span}(S) \geq 2|S| - 1$, and the intervals $S = \\{ \[2,3\], \[3,5\], \[5,6\] \\}$ have span $4 \< 2\cdot 3 - 1 = 5$.

---
Tags: algorithms, intervals
---


# Question
Title: Is the function that computes the minimum of a countable set computable?
Given $A$ a countable set of numbers and $\min$ the function returning the minimum of a set (if exists). Is $\min(A)$ computable? My first try is thinking $A$ as infinite list $A = \[a\_0, a\_1, a\_2,...\]$ such that $a\_i \< a\_j$ for every $i \< j$ and write a simple while program $P$ such that $P(A) = a\_0$. Is that correct? If so I wonder who is the equivalent μ-recursive function?

# Answer
> 1 votes
Your question lacks some details and without additionnal precisions, the answer is no.

For $n\in \mathbb{N}$, denote $S(n)$ the maximum number of steps that a Turing machine with $n$ states that take before halting with an empty input, on the alphabet $\Sigma = \\{0, 1\\}$. It is a well known fact that $S(n)$ is not computable.

Denote $E(n) = \\{S(k) \mid k \geqslant n\\}$. Since $S$ is an increasing function, it is clear that $\min(E(n)) = S(n)$. However, $E(n)$ is countable, therefore is a counter example to the property.

# Answer
> 1 votes
To make the question better defined, we must specify the initial countable set $A$ of natural numbers, so that the specification can be used as input for our computer. Thus we assume that there is a program $E$ that lists the elements of $A$ one by one, not necessarily in order. Thus $A$ is *recursively enumerable*.

Now assume that there is a program $P$ that computes the minimal element of a recursively enumerable set $A$ (given its program listing $E$). I claim that then we can list the elements of $A$ in their natural order. The minimal element $a\_0$ of $A$ is easily found, it can be determined by $P$ applied to $E$. But now $A\_1 = A - \\{a\_0\\}$ is also recursively enumerable: its program $E\_1$ use the program $E$ that enumerates $A$, except that it ignores $a\_0$ in its enumeration. Again we can apply $P$ to find the minimum but now for $A\_1$ and its enumerating program $E\_1$. The minimum $a\_1$ of $A\_1$ is the second element of $A$. We store $a\_0,a\_1$ and repeat, observing we have a program that enumerates $A\_2 = A - \\{a\_0,a\_1\\}$. Etcetera.

Hence we obtain that the recursively enumerable set $A$ can be enumerated in order. Equivalently, see elsewhere, the set $A$ is in fact *recursive* (meaning there is a program that decides membership in $A$). This is a contradiction, the recursive sets are a strict subset of the recursive enumerable sets.

Hence a program that computes the minimal element of a recursive enumerable (countable) set $A$ does not exist.

---
Tags: computability, mu-recursion
---


# Question
Title: If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?
L1, L2, and L are not finite. We're given that L and L2 are regular. However, L1 ∩ L2 is empty, since L2 is the complement of L1.

Is L1 regular under the property that regular languages are closed under union? I have been going back and forth about this for a while and any help would be appreciated. Thank you!

# Answer
> 1 votes
If $L\_1$ is the complement of $L\_2$ and $L\_2$ is regular then $L\_1$ must be regular since regular languages are closed under complement. Furthermore, since $L\_1$ and $L\_2$ are complements and $L = L\_1 \cup L\_2$, then $L\_1 = L - L\_2$ and regular languages are also closed under relative complement.

But if you are asking if we can infer that $L\_1$ is regular given only that $L\_2$ and $L$ are regular without the condition that $L\_1$ is complement of $L\_2$, consider any non-regular language $L'$ and the regular language $\Sigma^\*$. Notice that $\Sigma^\* \cup L' = \Sigma^\*$. So in general, the result of a union of a regular language and an arbitrary language can result to a regular language.

# Answer
> 1 votes
The language L1 is L \ L2. Take the FSMs for L and L2, create a new state machine whose states are pairs of states of these two FSMs, transitioning accordingly, and the accepting states are those that accept L but not L2.

Basically the same prove as for union or intersection or complement.

---
Tags: regular-languages, finite-automata, closure-properties
---


# Question
Title: Counting number of 1-hop paths in a sparse graph
Given a sparse undirected graph $G=(V,E)$ where $|E|=O(|V|)$, a one-hop path between a pair of vertices $(u,v)$ is a path in $G$ connecting $(u,v)$ where there is exactly one intermediate vertex between the vertices i.e. $u \leftrightarrow t \leftrightarrow v$ where $t$ is the intermediate vertex, $(u,t,v)$ are distinct vertices.

(actually I am not entire sure if 'one-hop' is the right terminology here. Let's assume it is).

I have $Q$ queries, where each query consists of a pair of vertices $(u,v)$ in $G$ and asks the question: how many distinct one-hop paths exist between the given pair of vertices. For this question let's assume $Q=O(|V|)$. All $Q$ queries are provided up-front and you do not have to answer the queries in the order given.

While I can solve this problem by counting the paths one by one for each query using an adjacency list, time complexity is $O(|V|^2)$. Is there a more efficient way to solve this?

PS: not a home work problem. Just something I have in mind.

# Answer
> 0 votes
I think this is possible in $\mathcal{O}(|V|\sqrt{|V|})$ for all $Q$ queries.

Assume the graph is represented as an array of adjacency sets: for $v\in V$, $G\[v\]$ is a set containing all neighbors of $v$.

Then the number of $1$-hops from $u$ to $v$ is the size of $G\[v\]\cap G\[u\]$. This can be computed in $\mathcal{O}(\min(\deg v, \deg u))$.

Now the problem is that if the $Q$ queries consists of the same query $(u, v)$, and it happens that $\deg u$ and $\deg v$ are $\mathcal{O}(|V|)$, that would result in total complexity $\mathcal{O}(Q|V|) = \mathcal{O}(|V|^2)$. To avoid that, you can create a hashtable, and each time you make a query, you can add the association $((u, v), n)$ to the hashtable. That way, the next time you have to make an already made query, its complexity would be $\mathcal{O}(1)$.

Now what is the worst that could happen? If you consider $V = \\{v\_1, …, v\_n\\}$ with $\deg(v\_1)\geqslant \deg(v\_2) \geqslant … \geqslant \deg(v\_n)$, the worst is that the queries would be $(v\_1, v\_2)$, $(v\_1, v\_3)$, $(v\_2, v\_3)$, …

If $Q \leqslant c|V|$, that would result is a complexity less than $$\sum\limits\_{j=2}^{\sqrt{2c|V|}}\sum\limits\_{i=1}^{j-1}\deg(v\_j) = \sum\limits\_{j=2}^{\sqrt{2c|V|}}(j-1)\deg(v\_j)\leqslant \sqrt{2c|V|}\sum\limits\_{j=2}^{\sqrt{2c|V|}}\deg(v\_j) = \mathcal{O}(|V|\sqrt{|V|})$$ The last equality holds true because $\sum\limits\_{v\in V}\deg(v) = 2|E| = \mathcal{O}(|V|)$.

Note that in this worst case, we considered an adversarial strategy. Since the average degree of any vertex is $\mathcal{O}(1)$, the average complexity would actualy be $\mathcal{O}(|V|)$ for all $Q$ queries.

---
Tags: graphs, combinatorics
---


# Question
Title: Turing machine for square root of n - transition table
How would someone create a Turing machine that computes ceil(sqrt(n))?

n = 1, 2, 3, 4, 5, 6, 7, 8, 9, ... =\> f(n) = 1, 2, 2, 2, 3, 3, 3, 3, 3 ....

And that I want the input tape to have n 1's in it to represent the number i.e. 5 would be #11111 How would the turning machine with transition table for this be created?

# Answer
> 3 votes
Try all squares increasingly until you exceed the input. For this, consider a process that erases the first digit, then the next three, the next five, the next seven and so on, while lengthening a sequence of ones. When the input is exhausted, you are done.

---
Tags: turing-machines, automata
---


# Question
Title: Minimal number of positive intervals to cover all positive elements
I'm struggling in finding a correct way to approach this, I'm aware that this problem is solvable using dynamic programming, and this problem somehow relates to the "max non-contiguous subarray" problem, yet I cannot make the connection.

Given an array of integers, $A=(a\_1,\ldots , a\_n)$ for which $\sum\_{i=1}^{n}a\_i\<0$.

A "Positive Interval" is defined to be a pair of indices $(i,j)$, $1\le i\le j\le n$ such that $\sum\_{k=i}^{j}a\_k\>0$

Describe an algorithm to return the minimal size of group $J$ containing positive intervals in such manner that for all $0\<a\_\ell\in A$, there is (at least) an interval $(i,j)$ in $J$ such that $i\leq\ell\leq j$.

The intervals can be overlapping, and negative numbers of $A$ dont have to take part in any interval of $J$.

For example, given $A=(1,7,-9,2,-10,-5,5,-10,4,-2,3,-1,2)$ , the algorithm should return $2$, since the "optimal" result would be: $$ J=\\{(1,4), (7,13)\\} $$ where positive interval $(1,4)$ "covers" elements $1,7,-9,2$ while positive interval $(7,13)$ "covers" elements $5,-10,4,-2,3,-1,2$.

# Answer
Here is a linear-time solution that consists of the following two parts.

#### Preparation: compute the prefix sums and the "milestones" among them.

1. Compute the prefix sum array $s$, $s\_i=\sum\_{k=1}^ia\_i$ for all $0\le i\le n$. This is done by setting $s\_0=0$ and then $s\_{i}=s\_{i-1}+a\_i$ for $i$ from $1$ to $n$.
2. A prefix sum $s\_i, i\>0$ is called a milestone if it is bigger than all following prefix sums, i.e., $s\_i\>s\_k$ for all $k\>i$.
Scanning $s\_{i}$ for $i$ from $n$ down to $1$, note down the successive strict maximum element found. Reversing the sequence we have noted down, we get all milestones $s\_{u\_1}, s\_{u\_2}, s\_{u\_3}, \cdots$ in the natural order, i.e., $0\<u\_1\<u\_2\<u\_3\<\cdots$ and $s\_{u\_1}\>s\_{u\_2}\>s\_{u\_3}\>\cdots$.

It takes $O(n)$ time to run this part.

#### Greedy: select the "strongly-positive" interval that covers the next uncovered positive element and the most elements after it

A pair of indices $(i,j)$, $i\<j$ is viewed as covering all elements in $a$ with indices between $i$ and $j$. It is a strongly-positive interval if it is a positive interval and both $a\[i\]$ and $a\[j\]$ are positive. Increasing $i$ and decreasing $j$ if necessary, we can change a positive interval to a strongly-positive interval. If a group of positive intervals cover all positive elements in $a$, we can change each of them whenever necessary so that they becomes a group of strongly-positive intervals that cover all positive elements in $a$ still. Hence it is enough to consider strongly-positive intervals only.

1. Let $\mathit{previous\\\_target} = -1$, $\mathit{right} = -1$ and $m=-1$.
2. Loop the following.

1. Try finding the nearest positive element after index $right$. If there is no such element, break the loop. Otherwise, let $\mathit{target}$ be its index.
    2. Among all strongly-positive intervals that cover that positive element, select the one that covers the most elements after that positive element. (If there are several such intervals, select any one of them. We only care about its right end.)

    1. Find the index $\mathit{left}\le\mathit{target}$ such that the sum of elements between $\mathit{left}$ and $\mathit{target}$ is as large as possible.
        That index must be larger than $\mathit{previous\\\_target}$; otherwise the interval $(\mathit{left},\mathit{target})$ is a strongly-positive interval that covers the element at $\mathit{previous\\\_target}$ whose right end is larger than $\mathit{right}$, the right end of the interval last selected, which contradict with how that interval was selected.
        2. Increase $m$ by $1$ repeatedly until $u\_m\ge\mathit{target}$.
        3. While $s\_{u\_{m+1}}\>s\_\mathit{left-1}$, increase $m$ by $1$ .

    The interval we then select is $(\textit{left}, u\_m)$. It can be shown this interval is strongly-positive and it covers $a\[target\]$. Furthermore, it covers the most elements after $a\[target\]$ among all such intervals. This "greedy property" ensures that the group of strongly-positive intervals we selected "stays ahead" of all other groups of the same number of strongly-positive intervals, i.e., covers no less positive elements since the front of $a$ without missing any positive element in between.
    3. Update $\mathit{previous\\\_target}$ with $\mathit{target}$. Update $\mathit{right}$ with $u\_m$.
3. Return the number of intervals we have selected.

It takes $O(n)$ time to run this part.

#### An implementation in Python

Please go here at replit.com and click the green "Run" button once or twice to run some basic tests.

Please view the function `minimum_positive_intervals(nums)` in file main.py that implements the approach above. You may need to click "show files" button and/or "main.py" button first.

Note that while the indices starts with $1$ in the question and this answer, all indices in the implementation starts with $0$.

#### What if we should also cover nonpositive elements?

The same analysis and algorithm applies, except that we will delete/adjust the requirement/phrases/steps that are related to element positivity.
> 1 votes

---
Tags: algorithms, dynamic-programming, arrays, greedy-algorithms, maximum-subarray
---


title: Compute Permutation Number

text:
# Question
Title: Compute Permutation Number
Given a permutation on the array of integers 1 through n, I want to find the index of the permutation in a list of all possible permutations of those integers, sorted in lexicographic order.

For example, given the permutation `{1, 3, 2}` with n=3, I want the program to return `1`, because the array has 6 permutations (`{{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}`), and when all the permutations are sorted in lexicographic order, the given permutation is at index 1.

A possible solution is to go through every permutation, but this takes O(n!) time. Is there a way to do this in polynomial time?

This problem seems somewhat related to this one, but isn't the same.

If it helps, I am looking to write the code for this problem in C++.

Any potential clarifications are welcome.

# Answer
A first observation is that for all $k\in \\{1, …, n\\}$, there are $(n-1)!$ permutations of size $n$ beginning with $k$.

For a permutation $\sigma = (k\_1, …, k\_n)$, that means that the rank of $\sigma$ is at least $(k\_1-1)\times (n-1)!$.

What you can do to find the exact rank is updating $(k\_2, …, k\_n)$ by replacing each $k\_i$ with $k'\_i$ such that: $$k'\_i = \left\\{\begin{array}{ll}k\_i&\text{if }k\_i\<k\_1\\k\_i-1&\text{otherwise} \end{array}\right.$$

The sequence $\sigma'=(k'\_2, …, k'\_n)$ is then a permutation of $\\{1, …, n-1\\}$. If $R\_n(\sigma)$ represents the rank of $\sigma$ among permutations of size $n$, then:

$$R\_n(\sigma) = (k\_1-1)\times (n-1)! + R\_{n-1}(\sigma')$$ This gives an algorithm in $\mathcal{O}(n^2)$ (assuming the computation of factorials is done in $\mathcal{O}(1)$, which may not be the case in the general case).
> 6 votes

# Answer
This task is known as ranking permutations. It can be solved with the factorial number system (https://en.wikipedia.org/wiki/Factorial\_number\_system). See also https://stackoverflow.com/q/1506078/781723, https://stackoverflow.com/q/39839119/781723 for further explanations.

More generally, see ranking and unranking (https://oeis.org/wiki/Ranking\_and\_unranking\_functions).
> 9 votes

---
Tags: optimization, permutations
---


# Question
Title: Why is Javacript's Object not a primitive data type?
If javascript's object is just associative array, what makes it non-primitive as they have labeled it? It is certainly already built in. Its not like I'm creating my own concrete implementation of associative array before i begin coding on it.

According to wiki's quote:

> **Primitive data types** or built-in data types are types that are built-in to a language implementation. User-defined data types are non-primitive types. For example, Java's numeric types are primitive, while classes are user-defined.

There is another quote

> Primitive types are almost always value types, but composite types may also be value types.

Why is primitive type mostly value type and not reference type? it doesn't have any correlations to the first quote 'built-in data types are types that are built-in',

https://en.wikipedia.org/wiki/Primitive\_data\_type

# Answer
> 1 votes
A term means exactly what the person using the term defines it to mean. No more, no less.

The ECMAScript Language Specification defines the term *primitive value* as follows:

> # 4.4.5 primitive value
>
> member of one of the types Undefined, Null, Boolean, Number, BigInt, Symbol, or String as defined in clause

> If javascript's object is just associative array, what makes it non-primitive as they have labeled it?

Because the definition of primitive in the ECMAScript Language Specification says so.

> According to wiki's quote:
>
> > **Primitive data types** or built-in data types are types that are built-in to a language implementation. User-defined data types are non-primitive types. For example, Java's numeric types are primitive, while classes are user-defined.
>
> There is another quote
>
> > Primitive types are almost always value types, but composite types may also be value types.
>
> Why is primitive type mostly value type and not reference type? it doesn't have any correlations to the first quote 'built-in data types are types that are built-in',

If the two quotes don't agree, then the most likely reason is that they were written by two different people who use two different definitions of the term "primitive".

Essentially, what you have here is four understandings of what the term "primitive" means:

* Yours,
* ECMASCript's,
* the first quote's author's, and
* the second quote's author's.

Before you start comparing statements and conclusions between those four, you first need to verify that all of those four use the same definitions of the terms you are comparing. I.e. you need to make sure that all four (including yourself) use the same definitions for terms such as "primitive", "composite", "user-defined", "built-in", "value type", and so on.

Just as an example: the first quote defines "primitive types" to be the same as "built-in types" and contrasts it with "user-defined types". The second quote contrasts "primitive types" with "composite types". So, the first quote is concerned with *who defines the type*, the second quote is concerned with *whether the type is made up of a single piece or multiple pieces*.

Those two are *completely different things*, so it should be no surprise that they come to different conclusions: for example, Objects are built-in types in ECMAScript, therefore, they are primitive according to the first quote, but they are also composite which means they are *not* primitive according to the second quote, and we have already established that they are also not primitive according to the ECMAScript Language Specification.

Note: you wrote that you found those quotes on the Wiki, but I couldn't find them anywhere on the Wiki, so I was not able to examine the wider context.

By the way, this is in no way specific to primitive types or to Computer Science or even to Science in general. E.g. the term "football" means very different things even to speakers of the same language, e.g. people from the UK or people from the US. In Germany, "liberals" are people who advocate for small government, against government spending, against social security and public healthcare, whereas in the US, those would be called "conservative" and liberals are the exact opposite.

---
Tags: data-structures, programming-languages
---


# Question
Title: Perform subtraction micro operation R3←R1-R2 where R1=1011 and R2=1100
From tutorials point:

> Subtract micro-operation are using minus operator we create 1's complement and add 1 to the register which obtains subtracted, i.e R1 - R2 is similar to R3 → R1 + R2' + 1

$$ R2'= 0011 $$

$$ R3=R1+R2'+1 \\\Rightarrow R3 = 1011+0011+1 \\\Rightarrow R3 = 1111 $$

This is obviously not the right answer, what am I doing wrong?

# Answer
As far as I know, $(-5)-(-4)=-1$ is correct.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Why does merge sort work for any $n$, but the basic FFT algorithm only for powers of $2$?
Merge sort and FFT are both divide and conquer algorithms that split the input in two repeatedly. While merge sort can be applied to any $n$, the FFT algorithm given in CLRS (section 30.2, third edition) only applies when $n$ is a power of $2$. How come we can forge ahead with any $n$ for merge sort, but not quite for FFT?

# Answer
**Short answer:**

A merge works with individual elements. Any numbers can be handled. In particular, *natural* mergesort does merge sequences of arbitrary lengths.

The FFT works on pairs of elements, with no leftovers. So there must be an even number of them, and by recurrence, a power of $2$.

---

Variants of the FFT can be based on other primes, and can be combined to work for composite $n$, but they don't reach the efficiency of binary FFT.
> 1 votes

---
Tags: divide-and-conquer, mergesort, fast-fourier-transform
---


title: Mapping reduction - Bit Flip

text:
# Question
Title: Mapping reduction - Bit Flip
Let $L=\\{\<M\> | M$ is a TM, $L(M)\ne \emptyset$ and $\forall x\in L(M), \overline{x} \notin L(M) \\}$

While $\overline{x}$ is the bit flip of $x$.

I want to show a mapping reduction to prove that this language is either in R / RE / coRE or none of them.

My intuition is that this language does not belong to any of the classes, so I am trying to show to reductions:

$\overline{E\_{TM}} \le\_m L$ and $E\_{TM} \le\_m L$.

Am I in the right direction?

Because I can't find any mapping function to help me with that.

Thanks a lot!

# Answer
These are just ideas, not actual redcutions.

The language indeed seems to be neither RE, nor coRE. It might help to identify what part of the language makes it not RE or not coRE:

* the $L(M)\neq \emptyset$ is a RE part: it can be verified by dovetailing. However, the $\forall x\in L(M), \overline{x}\notin L(M)$ property cannot be verified: not only you'd need to browse all possible $x$, the property $\overline{x}\notin L(M)$ cannot be verified. What I suggest is trying to make a reduction from $L\_{\forall} = \\{\langle M\rangle \mid L(M) = \Sigma^\*\\}$, a well-known non-RE language, to your language. To not be bothered by the first part, you just have to guarantee that your reduction create a MT with a non empty language.
* the $\forall x\in L(M), \overline{x}\notin L(M)$ part is coRE: you "just" need to find a $x$ such that $x\in L(M)$ and $\overline{x}\in L(M)$ as a counter-example. This can be done by dovetailing. However, the $L(M)=\emptyset$ is not a coRE part: you'd need to verify for all $x$ that $x\notin L(M)$. This cannot be done. I suggest here that you make a reduction from $L\_{\emptyset} = \\{\langle M\rangle\mid L(M) = \emptyset\\}$, a non-RE language, to the complement of your language. To not be bothered by the second property, just insure that for all $x\in\Sigma^\*$, $x\in L(M) \iff \overline{x}\notin L(M)$.

Hope that helps.
> 1 votes

---
Tags: complexity-theory, computability, automata, reductions, mapreduce
---


# Question
Title: Are "almost all" decidable languages not in P?
There's a famous classical circuit complexity result by Shannon that says almost all languages require exponential circuits \[\[1\]\], proven by comparing the number of distinct circuits of $n$ variables versus the number of boolean functions of $n$ variables.

Similarly, there's a result that "almost all" languages are undecidable, because the set of TMs is countable while the set of languages is uncountable.

**Question:** is there a result of similar flavor about complexity classes? E.g. something like `"almost all" decidable languages are not in P`?

The question seems interesting to me because it's much less clear how to even define "almost all". Both sets here are countably infinite so cardinality arguments don't work. We could maybe do something like $$\lim\_{n \to \infty} \frac{\text{# of polytime TMs with n states}}{\text{# of total TMs with n states}}$$ ? But that's obviously tremendously complicated and out of reach. Are there simpler definitions that would capture a similar meaning?

# Answer
> 1 votes
This answer relates to the number of decidable languages (and not the number of TMs that accept decidable languages).

So my intuition would say no, there sre no more decidable problems not in P than the problems in $P$, since you can reduce a problem $L$ of running time $O(f(n))$ into a problem $L’=\\{w0^{f(|w|)}|w\in L\\}$ in $P$, i.e. we add many zeros to each instance, to make the size of the input large enough, that the original algorithm has linear running time on the resulting instance.

Note that this is not a complete proof, but I would assume you can use this fact to build a proof.

Note also that such a reduction is not really interesting (we can’t really use it to make any complexity assumptions about membership of $P$) since the reduction itself is not computable in log space and it is not even in FTIME(g(n)) for any computable g, since you can always choose a harder problem to begin with.

---
Tags: complexity-theory, time-complexity, asymptotics
---


# Question
Title: Perfect hash function that weakly preserves leading zeros
I need a perfect hash function that maps 2 integers into one integer twice the size (i.e. $(Int64, Int64) \rightarrow Int128$).

The function preserves sum of leading zero bits:

* $(0, 0) \rightarrow 0$ \- good mapping, as each argument has $64$ leading zeros and that transformed into $128$ leading zeros of the output
* $(0, 0) \rightarrow 27$ \- also good mapping, output `0x11011` still has $123$ leading zeros
* $(2^{30}, 2^{15}) \rightarrow 2^{43}$ \- good mapping, sum of arguments zeros is $33 + 48 = 81$ which is close enough to output's $84$
* $(0, 0) \rightarrow 2^{50}$ \- bad mapping, only $77$ zeros in the output
* $f(a,b) = a × b$ preserves zero sum well but is not a perfect hash function

1. It's fine if the function doesn't work well with a small subset of arguments: $1\\%$ of all pairs violates weak zero sum preservation is acceptable, but the function still should be a perfect hash function.
2. The function should not use additional memory like lookup tables.
3. If $z(x)$ is the number of leading bits then zero sum is $N$-preserved if $| z(x) + z(y) - z(f(x,y))| \leq N$, I'm looking for $N \leq 3$, but $N \leq 6$ are good enough.

# Answer
> 1 votes
Consider the sequence $S$ which enumerates pairs $\langle s,t \rangle$ of 64-bit strings, with the following ordering:

* If $z(s)+z(t) \< z(s')+z(t')$, then $\langle s,t \rangle$ is listed before $\langle s',t' \rangle$.
* If $z(s)+z(t) = z(s')+z(t')$ and $z(s) \< z(s')$, then $\langle s,t \rangle$ is listed before $\langle s',t' \rangle$.
* If $z(s)=z(s')$ and $z(t)=z(t')$ and the concatenation $s\\, t$ comes lexicographically before the concatenation $s' \\, t'$, then $\langle s,t \rangle$ is listed before $\langle s',t' \rangle$.

Consider the sequence $T$ which enumerates 128-bit strings $u$, with the following ordering:

* If $z(u) \< z(u')$, then $u$ is listed before $u'$.
* If $z(u)=z(u')$ and $u$ comes lexicographically before $u'$, then $u$ is listed before $u'$.

Now consider the mapping that maps from a pair $\langle s,t \rangle$ to its index in $S$, call the result $i$, then finds the $i$th item in $T$, and outputs the result. This then is a perfect hash function, and I believe it satisfies your desired property. Moreover, it is possible to compute both mappings (i.e., the ranking in $S$ and unranking in $T$) fairly efficiently. Therefore, the hash function can be computed fairly efficiently.

---
Tags: hash, hashing
---


# Question
Title: Using hypercomputation for "impossible" problems?
In mathematics and philosophy there are some unsolvable problems like Russell's paradox or the liar's paradox that are usually said to be undecidable... There are also other "impossibilities" such as finding positive integers to divide a prime number other than the number itself and 1.

However, could we use some kind of hypercomputer or an oracle that could theoretically give the solutions to these problems? Perhaps through some special kind of computational processes based on alternative forms of logic?

# Answer
> 5 votes
Nope.

Russell's paradox and the liar's paradox aren't undecidable. They aren't even decision problems.

As far as we know, hypercomputers don't exist. They are an imaginary idea that don't appear likely to exist in the real world. We use them as a thought experiment to imagine what the consequences would be if we had a hypothetical device that could do something that no computer can do. So, no, you can't use them to do anything in the real world since they don't exist.

In any case, no, hypercomputers, even if they existed, would not solve those paradoxes, because those paradoxes are not undecidable decision problems -- they aren't even decision problems, so computability is basically irrelevant to them.

---
Tags: computability, logic, oracle-machines, philosophy, hypercomputation
---


# Question
Title: How to determine if an automata (DFA) accepts an infinite or finite language?
Given an automata \[DFA $A=(Q,Σ,δ,q\_0,F)$\], is there a way to determine whether it accepts an infinite or finite language?

# Answer
This is well enough known that you should be able to find it in most intro theory texts:

**Theorem**. The language accepted by a DFA $M$ with $n$ states is infinite if and only if $M$ accepts a string of length $k$, where $n\le k \< 2n$.

This makes the decision problem simple: just try all strings of length at least $n$ and less than $2n$ and answer "yes" if $M$ accepts one of them and "no" if there's no string in that range that's accepted.
> 15 votes

# Answer
On Drawing a DFA , if there are loops in states then there is a possiblity that automata accepts infinite language .

Whereas if there are no loops in a DFA , then it certainly accepts finite language .
> 6 votes

# Answer
You can easily calculate for each state the set of states that can be reached from that state.

The CFA accepts an infinite number of inputs if there is a state X with the properties: X can be reached from the initial state, X can be reached from X, and some terminating state can be reached from X.
> 3 votes

# Answer
A DFA accepts infinitely many strings iff there exists a loop in the path from initial state to final state.
> 0 votes

# Answer
To prove why we only need to check strings of length within $\[n,2n)$. It is sufficient to prove the following statement. If a DFA $D$ with $n$ states accepts infinite many strings, then $D$ accepts some string $s$ whose length falls in $\[n,2n)$.

Suppose it is not the case, then $\forall u\in L(D)$, length of $u$, denoted as $\text{len}(u)$ must either has $\text{len}(u)\<n$ or $\text{len}(u)\geq 2n$.

As $D$ accepts infinite many strings and the set $\\{u\in L(D)~|~\text{len}(u)\<n \\}$ is finite, $S=\\{u\in L(D)~|~\text{len}(u)\geq n\\}\neq \emptyset$. Choose a $z\in S$, where such $\forall u\in S $ we have $ \text{len}(z)\leq \text{len}(u)$. As $\text{len}(z)\geq n$ (hence $\text{len}(z)$ $\geq 2n$), it must contain a loop. Aka, it admits a decomposition $$z=ab^mc.$$ Where $n\geq \text{len}(b)\geq1$. This further imposes $$z'=ab^{m-1}c \in L(D).$$ Note that $\text{len}(z')=\text{len}(z)-\text{len}(b) \geq 2n-n=n.$ This imposes $z' \in S.$ However, $\text{len}(z')\<\text{len}(z)$ contradicts with the minimality of length of $z$. A contradiction arises and the statement at top holds at the first place.
> 0 votes

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


# Question
Title: How is the input to a BROUWER algorithm done
The Brouwer fixpoint theorem states that any continuous mapping $f$, from a convex, compact set to itself will contain a fixpoint.

The Brouwer algorithm finds these (approximate) fixpoints. But how is a continuous function inputted into this algorithm?

Is it as a black box? If so, would changing this to a discrete set of points change the complexity of the algorithm?

# Answer
There are several ways to formalize the BROUWER problem. The most intuitive is to have $f$ specified by an arithmetic circuit, as in Etessami and Yannakakis, On the complexity of Nash equilibria and other fixed points. However, this version is not known to lie in PPAD (see this tutorial of Etessami).

To fix this, we can either restrict the circuit to be piecewise linear, as in Etessami and Yannakakis; or ask that the function be Lipschitz with an explicit constant, as in Rubinstein, Settling the complexity of computing approximate two-player Nash equilibria; or use a discretization which corresponds to a (highly restricted) piecewise linear function, as in Daskalakis, Goldberg and Papadimitriou, The complexity of computing a Nash equilibrium.
> 9 votes

---
Tags: algorithms, reference-request, fixed-point
---


# Question
Title: Maximum Flow algorithm. How to prove the following statements
Good Evening,

So I am trying to solve this exercise which is a paticular case of maximum flow algorithm. Here the graph must have all even edges and 1 odd edge and it must have a maximum flow that is odd.

Now I need to prove the following two points which state that the single odd edge must have a flow $\>1$ and/or that edge must have maximum flow in it with respect to its capacity.

I understand that running certain algorithms to find odd flow in such cases prove that both statements are correct that is there is a flow $\>1$ in odd edge and also there is maximum flow always in that odd edge. But I don't know how to prove it formally.

Question text:

Consider a graph $G=(V,E)$, with integer capacities on the edges, such that for all $e\in E\setminus\\{e^∗\\}$, it holds that $c\_e$ is an even number, and $c\_{e^∗}$ is odd. Suppose that there is a maximum flow in this graph with odd flow.

a. Prove/Disprove: It must be that in every maximum flow, there is a flow in $e^∗$ (i.e., $f\_{e^∗}\>0$).

b. Prove/Disprove: It must be that in every maximum flow, there is a full flow in $e^∗$ (i.e.,$f\_{e^∗}=c\_{e^∗}$).

# Answer
The Max-flow/Min-cut theorem can be used to prove this property.

As a reminder, $f$ is a max-flow if and only if there exists a cut $X$ of capacity $|f|$.

Let $f$ be a max-flow of odd value in $G$.

a. Suppose there is no flow through $e^\*$. Then in $G\[V\setminus\\{e^\*\\}\]$, $f$ is still a max-flow. However, since all edges have even capacity, all cuts have even capacity. Contradiction.

b. The same idea can be used, I will let you try to find the details.
> 0 votes

---
Tags: algorithms, graphs, network-flow, ford-fulkerson
---


# Question
Title: Finding majority element in $\mathcal{O}(nlogn)$ time
I am trying to build the logic behind a divide and conquer algorithm that will find the majority element in a matrix $A$ with $n$ elements in $\mathcal{O}(nlogn)$ time.

I thought that in order to make it divide and conquer, I'd need to split the array in two parts. By definition the majority element would be the one that appears in the array at least $\frac{n}{2}$ times. So, naturally, that means that at any time and with any sorting of the array one half of the two will have the overall majority element as its element. Therefore, finding the majority element recursively in either part will lead to my finding the overall.

Let's say that we start with the base of 1 element. So, if the array only has one element then that one is the majority element. But if the array has 2 or more elements, then we devide in two parts, left and right.

Here is where my problem occurs. The major element in either part could be the same, so then it obviously is the one. But if they are different, then how do I choose between the two. I'll give an example if it better explains my problem.

array = \[2,2,4,5,1,2,8,2\], majority element = 2, count = 4 = 8/2 = length(array)/2

split 1: \[2,2,4,5\] and \[1,2,8,2\]

split 2: \[2,2\] , \[4,5\], \[1,2\], \[8,2\]

split 3 would be the independent elements.

The algorithm will start from left to right, so first we get majority element on the left = 2 with count = 1 and majority element on the right = 2 with count = 1. They are equal so majority element = 2, count = 2.

Then we go to \[4\] and \[5\] where clearly each is the majority element of its side. So, how do we choose between those? Like suppose that 5 was instead 2, in which case not choosing 2 which would be the majority element could alter the count which would determine its majority.

Do I have a flaw in my way of thinking? Is this thought process completely wrong? I feel like I'm almost there but have to just determine how I'll choose if the majority elements are not equal.

# Answer
> 0 votes
The idea is to keep track of a "majority candidate" with each recursive call. When trying to merge solutions, if majority candidates are different in each half, you just need to browse the array to check which one appear more than the other. The most frequent will become the new majority candidate.

Let $T(n)$ denote the worst case complexity for an array of length $n$. Given the algorithm, it would verify:

$$T(n) \leqslant 2T\left(\frac{n}{2}\right) + \mathcal{O}(n)$$

The first part corresponds to the recursive calls, and the second part to the verification in case there are different candidates. That would indeed result in time complexity $\mathcal{O}(n\log n)$, but would actually be $\mathcal{O}(n)$ if there is no (or few) cases with multiple candidates.

Note that, as you said, this divide-and-conquer strategy will only work if there is a strict majority, otherwise you could be traped with equality cases. For example, if the array is $\[1, 2, 3, 2, 7, 2, 9, 2\]$, then each recursive call chosing a candidate among $\[1, 2\]$, $\[3, 2\]$, $\[7, 2\]$ and $\[9, 2\]$ could pick the wrong one. If there is a strict majority, the real majority element will always be picked at least once.

Also keep in mind that a matrix is just a fancy array.

---
Tags: arrays, divide-and-conquer
---


# Question
Title: In computational creativity, how do you measure how creative something is?
In computational creativity, how do you measure how creative something is?

Let's say you have to compare a piece of music written by Bach and then compare it to Chopin, how would you evaluate how creative they are and compare them both by giving them scores? How would the model work, are there existing models, and how does computational creativity define creativity in the first place?

# Answer
You can't. Creativity is subjective. There is no such metric.
> 0 votes

---
Tags: computability
---


# Question
Title: Aggregate method for dynamic table (amortized analysis)
For amortized analysis (aggregate method), dynamic table insertion cost can be divided into:

if no expansion, then cost = 1 if we expand the table, then cost = i (if i-1 is an exact power of 2)

then the total cost is

I don't understand how to get 2n from the part that I circle below

# Answer
It should be an inequality, using the formula for the sum of a geometric series: $$ \sum\_{j=0}^m 2^j = 2^{m+1} - 1. $$ Substituting $m = \lg n$ gives $$ \sum\_{j=0}^{\lg n} 2^j = 2^{\lg n+1} - 1 = 2n-1. $$
> 0 votes

---
Tags: algorithms, amortized-analysis, dynamic-array
---


# Question
Title: Given a list of numbers L and a target k, is there a subset of numbers from L whose product is k?
Is there any dynamic way of solving this problem? I would thank any help, I know the Subset sum Problem, but for solving it dynamically u have to create a matrix but here is not posible as the colums may not to be integers.

# Answer
> 0 votes
It’s a nice problem.

If all numbers were given factored into products of prime powers, say 2^2\*3^2 instead of 36, or 2^3835857109 instead of a billion digit number then the problem would be NP complete - restricting all numbers to be powers of two would produce the subset sum problem if we just look at the exponents. But writing the numbers as decimal numbers blows up the problem size. I don’t think the subset sum problem with limited size of numbers is NP-complete. (I may be wrong, anything about that would be appreciated).

It seems obvious to factor the numbers. But if we have a 100 digit number which might be a 100 digit prime or the product of two 50 digit numbers, that is hard.

But whether x is prime or the product of two large primes may be irrelevant. What we do: We pick any 2 numbers x, y in the problem and calculate g = gcd (x, y), and if g is not 1 then we replace x by g * (x/ g) and y by g * (y/g), until all pairs of numbers are examined and all gcds are \> 1. This is easily done in polynomial time. If a large x could be a product p\*q, but no other number has a factor p or q, then it is irrelevant whether x is prime or not. And while factoring 100 digit numbers is hard, calculating the gcd is easily done in quadratic time in the number of bits of the numbers, much smaller than the actual numbers.

So now we write each $L\_i$ and the target $k$ as products of $x\_j^{e\_j}$, and we need a subset of the $L\_i$ so that for every $j$, the sum of exponents of $x\_j$ for the subset of $L\_i$ matches the sum of exponents in $k$. The problem is NP-complete but only because we decreased it's size massively.

First step we throw out all numbers that don't divide k (have a factor $x\_i$ that is not a factor of k, or a factor raised to a higher power). Then for every $x\_j$, we count the exponents: If the members of $L\_i$ have a smaller sum of exponents than k, then there is no solution. If they have exactly the same sum, then the solution contains all numbers with a factor $x\_j$ (and others); we check that their product divides k. If not there is no solution. If yes, the solution includes those $x\_j$, so we write this down, then remove them from L, and divide k by their product.

There may be other cases where we can determine a solution, for example if we have three numbers with factors $x^2$, $x^3$ and $x^4$ and k has a factor $x^1$ to $x^9$ then each factor can be produced in exactly one way or not at all. And every time we have found a part of the solution, we may continue and find more parts that were not there before. And every time we reduce k, some $L\_i$ might not divide k anymore and can be removed.

You can come up with more complicated rules that force a part of the solution. At some point you are finished and have to go to backtracking. You take one $x\_j$ and assume it's part of the solution. Then you remove it from the problem, dividing k by $x\_j$, and try to solve the remaining problem. You find a solution, or you try another $x\_j$. For example, if k has a factor $x^1$ then your solution must contain exactly one number with a factor $x^1$ so that is what you try.

---
Tags: dynamic-programming, np, decision-problem
---


title: Show problem is NP-hard

text:
# Question
Title: Show problem is NP-hard
I'm preparing for my exam and I got stuck on the following problem:

The gardening problem:

> We have access to a set of different types of seeds and a number of plant pots.For each plant pot, there is a limit to how many seeds can be planted in that particular pot.
>
> In addition, there are seeds that cannot be planted in the same pot. These requirements are described by a list of pairs of seeds that do not want to be planted in the same pot. Each seed is featured in at least one pair in the list.
>
> The goal is to plant as many different types of seeds as possible, given the number of seeds that can be planted in each pot and a list of pairs of seeds that can't grow in the same pot.

I am supposed to formulate the gardening problem as a decision problem by introducing a goal K, and then show that this decision problem is NP-complete. I must show that it is included in NP and by designing a polynomial Karp reduction between the NP-complete problem **Independent set** and the gardening problem.

In order to show that a problem is included in NP I know that I must show that a given solution can be verified in polynomial time (this doesn't seem too difficult). It's the Karp reduction I'm a bit unsure how to do and need help with. I get confused by the different capacities of the pots.

*My solution so far:*

The gardening problem as a decision problem:

**Input**: List including the seed limit of each pot *M=\[m1,m2,...,mn\]*, a list of pairs of seeds *P={{fi, fj}}* that cannot be planted together, positive integer *K* (goal).

**Question**: Is it possible to plant **at least** *K* different types of seeds?

*(Should I exclude the "at least"?)*

In order to show that the problem is NP-hard I need to reduce the NP-complete problem **Independent set** to the gardening problem.

> ```
> IndependentSet(G=(V,E), K')=
>
> M ← [K'] // Only one pot with capacity of K'
> P ← E
> K ← K'
> return GardeningProblem(M, P, K)
>
> ```

The reduction is polynomial. I want to show that it is correct, i.e. there exists an independent set *I* with *K* nodes iff there exists seedbed *S* with *K* seeds that can be planted together.

If there is a solution to the IS problem of size K, we can put the K corresponding seeds into our pot - therefor if we can't put K seeds in our pot, there is no independent subset of size K.

Assume that *I* is an independent set in *G* with *K* nodes. Let *S* be the corresponding seeds *I*. Take two arbitrary seeds *fi* and *fj* in *S* and show that they can be planted together. The fact that *I* is an independent set means that:

> *vi*,*vj**I* → (vi, vj) ∉ E → *{fi, fj}**P**fi* and *fj* can be planted together.

The other implication, assume there exists a seedbed *S* where |*S*| = *K* and seeds that can be planted together. Then:

> *fi*,*fj**S**{fi, fj}**P* → (vi, vj) ∉ E → *vi* and *vj* are independent.

Thus, the proof is complete.

I get a bit confused by the fact that the pots can have different capacities, and I don't really know how to work with that. It feels like I am missing something and that I should take the different capacities of the pots into consideration in the proof. It is supposed to be an easy problem. Is there a better way to solve this?

And when I formulate the gardening problem as a decision problem, I'm not sure if the "Question" should be "...*at least* K different types of seeds" or just "...K different types of seeds" ? How do I know which one is correct?

If someone could tell me if something is missing it would be greatly appreciated!

# Answer
> 0 votes
The proof seems ok to me. The fact that you didn't use multiple capacities does not mean something went wrong: some problems are inherently more complex than others, and a reduction from a simpler problem to a more complex problem is generally easier.

For example, doing a reduction from the $\texttt{Clique}$ problem to the $\texttt{Subgraph isomorphism}$ problem is very straightforward: just ask if a $k$-clique is isomorphic to a subgraph of $G$.

For your other question, despite the problem of "at least $K$ seeds" and "exactly $K$ seeds" are slightly different, solving those is equivalent: the second one implies the first one, and if there is a solution planting more than $K$ seeds, there necessarily exists a solution planting exactly $K$. That's why you can just choose the variant you are more comfortable with.

---
Tags: np-complete, reductions, np-hard, np, polynomial-time-reductions
---


# Question
Title: What is the name of the complexity class for the optimization version of co-NP-complete and coNexpTime-complete problems?
I know that the optimization version of NP-complete problems belong in NPO. What about co-NP-complete problems? Is there a co-NPO class, or is it just NPO?

I've also never seen the name for the complexity class of optimization problems whose decision version is NExpTime-complete. Is it called NExpTimeO? Is there a co-NExpTimeO complexity class?

# Answer
> 2 votes
There is no difference between $\mathsf{NPO}$ and what you would call $\text{co}\mathsf{NPO}$.

To explain why, I will try to use a problem as an example:

* the problem $\texttt{Clique}$ is defined as follow:

> Input: an undirected graph $G$ and an integer $k$.
>
> Question: does $G$ have a $k$-clique as a subgraph?

It is well known that this problem is $\mathsf{NP}$-complete.
* the problem $\text{co}\texttt{Clique}$ is the corresponding $\text{co}\mathsf{NP}$-complete problem and is defined as follow:

> Input: an undirected graph $G$ and an integer $k$.
>
> Question: does $G$ **NOT** have a $k$-clique as a subgraph?
* the problem $\texttt{MaxClique}$ is the corresponding optimisation problem:

> Input: an undirected graph $G = (V, E)$.
>
> Solution: a subset $V'\subseteq V$ such that $G\[V'\]$ is a clique.
>
> Optimization: maximize $|V'|$.

Now if you are able to solve the optimisation version $\texttt{MaxClique}$, you can find the maximal size of a clique in $G$. Given this answer, you can find the answer to both the $\texttt{Clique}$ and the $\text{co}\texttt{Clique}$ question on the same graph, for any $k$. See here for a formal definition of $\mathsf{NPO}$; you can see that it coincides with a definition we would give for $\text{co}\mathsf{NPO}$.

As for your other question, I think that $\mathsf{NEXPTIME}$ is often only called $\mathsf{NEXP}$, and the optimisation version would be $\mathsf{NEXPO}$ (and for the same reason as above, there is no $\text{co}\mathsf{NEXPO}$ to consider). But this doesn't seem really studied, for example the complexity zoo doesn't mention it.

---
Tags: complexity-theory, optimization, complexity-classes
---


title: NP-Complete Reduction

text:
# Question
Title: NP-Complete Reduction
Prove the following problem is NP-Complete:
The problem gave a directed graph G, and several subsets of vertices of such graph are being specified as T1,T2,....Tn, and the subsects could intersect, does there exist a path in G where it doesn't contain any cycle and for every subsect Ti, the path consist of exactly 3 vertices from Ti?

On the proving part I've found the certificate to verify such problem but I'm stuck on the reduction process and cannot think of a previously-exist NP-Complete problem to reduced to, I've thought of TSP, Dir-Ham Cycle and even 3SAT,For the TSP I've though about picking vertices from each subset and form a map based on such, if there exist a specific combination of vertices along with a path resulting a specific value then we can say yes to the question, however that's a bit brutal force rather than polynomial, but TSP in my perspective is the most reasonable for this condition, I've though about dir ham-cycle but the intuition still falls apart, may I please get some assist on what direction should I approach it with?

# Answer
> 1 votes
I think a reduction from $\texttt{Directed Hamiltonian Path}$ (not cycle) would work quite well.

Given a digraph $G = (V, E)$ where $V = \\{v\_1, …, v\_n\\}$, consider the digraph $G' = (V', E')$ where:

* for all $i \in \\{1, …, n\\}$, $T\_i = \\{v\_{i,1}, v\_{i,2}, v\_{i,3}\\}$;
* $V'$ consist of three copies of each vertex $v\_i$: $\bigcup\limits\_{i=1}^n T\_i$;
* $E' = \\{(v\_{i,3}, v\_{j,1})\mid (v\_i, v\_j)\in E\\} \cup \bigcup\limits\_{i=1}^n\\{(v\_{i,1}, v\_{i,2}), (v\_{i,2}, v\_{i,3})\\}$, meaning that for each edge $v\_i\rightarrow v\_j$, you create $v\_{i,3}\rightarrow v\_{j,1}$, and for each vertex $v\_i$, you create a path $v\_{i,1}\rightarrow v\_{i,2}\rightarrow v\_{i,3}$.

It is clear that this construction can be done in polynomial time in the size of $G$.

Now, $G$ has a Hamiltonian path if and only if there is an acyclic path in $G'$ containing exactly $3$ vertices from each $T\_i$. Can you see why?

---
Tags: np-complete, np, decision-problem
---


# Question
Title: Does "strongly-polynomial time" implies "polynomial time in the unit-cost model"?
Consider any computational problem in which the inputs are integers. As far as I understand, if the problem has a strongly-polynomial time algorithm, it means that the algorithm uses a polynomial number of arithmetic operations in integers, and polynomial space.

Now, suppose we want to solve the same problem but the inputs are real numbers, and we have a computer that can do infinite-precision arithmetic operations on real numbers in unit cost. Can we use the same strongly-polynomial time algorithm to solve this problem in polynomial time?

What I found so far: the Wikipedia page on linear programming presents two open problems related to linear programming: "Does LP admit a strongly polynomial-time algorithm?" and "Does LP admit a polynomial-time algorithm in the real number (unit cost) model of computation?" and says that they are "closely related"; my question is whether a positive answer to the first question implies a positive answer to the second question?

# Answer
No. For instance, consider the following algorithm to compute the square root of the input $x$: use binary search on $t$ (computing $t^2$ in each iteration) to find the largest $t$ such that $t^2\le x$. This is a strongly polynomial time algorithm, but converting it to infinite-precision arithmetic does not give an algorithm to compute the square root on an infinite-precision input in polynomial time.
> 2 votes

---
Tags: polynomial-time, real-numbers
---


# Question
Title: Letter Boxed Puzzle - Is a minimum set cover plus additional constraints solution viable?
Upfront, I'm not a computer science or mathematics graduate. I am a dabbler/recreational programmer and I find some problem/solution scenarios intellectually stimulating to attempt. Sometimes (frequently, actually), this lack of formal training limits my ability to formulate a good solution to a problem. I can pretty much always come up with a brute force solution, but that's never really fulfilling (especially if takes the age of the universe to run)! Better algorithms can almost be seen as things of beauty and help me learn more and equip me to tackle more challenging problems.

So, here's the problem I'm attempting to solve currently but not sure of the best approach. The New York Times’ daily Letter Boxed puzzle requires the player to input words using ONLY the 12 letters given (3 on each side of a square) but with some constraints...

1. word length \> 2,
2. consecutive letters cannot be from the same side of the square,
3. whilst the 1st word is constrained only by 1 & 2 above, subsequent words must start with the same last letter of the previous word.

The object is to use all the 12 letters using a number of words \<= a number given for the puzzle – it’s “par”. (I’ve only seen this par as 4, 5 or 6 words).

My thinking is along these lines. As candidate words by definition need to have to be made from the 12 letters supplied, they are sub sets. Hence, the minimum set cover problem came to mind. Reducing the number of candidates sets was the second thing that came to mind and I thought it could be done this way...

A. In terms of letter constraints, a list of words can be pre-processed to remove words less than 3 letters long as well as double letters (they would violate constraint 2). This is generic as it works for ALL problems so the word dictionary I used is in this state.

B. Further pre-processing can then be done based on the 12 letters given for the particular puzzle to be solved. For each side of 3 letters, there are 6 letter pair combinations (doubles having already taken care of in A), so 24 such pairs in total that cannot appear in any word (constraint 2 again). All words containing these pairs can also be removed leaving a much smaller list of candidate words.

C. A final stage of pre-processing can be done which ensures that any words that contains a letter NOT in the 12 given is removed.

In using A, B & C I can get a dictionary of 50k words down to less that 1000 candidate words.

Implementing a minimum set cover (an exact cover may not always be available) wouldn’t be too difficult given the resources online. However, where I’m really stuck is understanding how to incorporate constraint 3 into the process.

So, is there a way or have I selected the wrong approach and need to go back to the drawing board?

---

Edit:

Having thought on this some more, I now think that I can incorporate constraint 3 as a "filter" when selecting from sets as per the greedy algorithm.

What I have experienced in the testing I've done with a particular puzzle is that the word with the biggest cover (i.e. that one that the greedy algorithm would choose first) does not facilitate using another word due to the last letter/first letter constraint. It contained 9 of the 12 letters but ended in a 'y'. No other word could follow that started with 'y' and contained any of the remaining 3 letters required for a solution. So I'm thinking something iterative that starts with the next best candidate if no solution is found using the best candidate.

I am also aware that most solutions published on the website are made up of just 2 words and is also dependent on what words are in the dictionary I use.

# Answer
> 0 votes
I expect that a brute-force solution will suffice. Enumerate all possibilities for the first word; for each such, enumerate all possibilities for the second word that respect constraint 3 and don't re-use any letter found in the first word; for each such, enumerate all possibilities for the third word; etc. You can truncate the search any time the resulting words total to 12 or more letters. I expect this will be fast enough that it's not worth trying to find a more clever solution.

---
Tags: algorithms
---


# Question
Title: Finding a minimal set of package versions in a dependency graph with constraints
Suppose you have a dependency graph of "packages" registered in the ecosystem of a given programming language. We can model each package as a tuple `(name, version)` where `name` is the package name (like `Plots`) and `version` is a semantic version number (like `1.2.3`).

Each package has a set of dependencies, which may include constraints. Perhaps `Plot-1.2.3` depends on `JSON` with a constraint `>= 1.0 && < 3.0`. Thus, there could be a number of `JSON-X.Y.Z` versions that are compatible with `Plot-1.2.3`.

The goal of this problem is to construct a "minimal" set of nodes to form a useful package snapshot.

Let's define a "useful" package snapshot as following:

1. It contains the *latest version* of every package.
2. Every package in the snapshot is "resolvable" (EDIT: as long as it's resolvable in the original ecosystem), i.e. the snapshot must include a compatible version of every necessary dependency of that package.
3. Every two packages in the snapshot are "pairwise resolvable," meaning that if there is a working set of dependencies to install them simultaneously in the original ecosystem, then there is also such a working set in the snapshot. (EDIT: note that when you're installing a set of packages, you only get to choose one version of a particular dependency package. Thus, if packages P and Q both depend on dependency D, pairwise resolvability means that there must be *one single version of D* compatible with both P and Q in the snapshot, as long as such is true in the full ecosystem.)

By this definition the full ecosystem is a useful snapshot. But the key part of this goal is "minimal." I want to find the smallest useful package snapshot that satisfies the rules above. I feel like there must be some prior art or theory that can help here. Graph coloring? Satisfiability? Please help :)

---

In case it's of interest, this is a real problem -- I want to package such a snapshot in the Nix package manager, so that a user can express something like "Please give me an environment with packages A, B, and C" and get a working environment with the latest version of those packages, as long as such is possible. There are about 80,000 nodes in the real graph. The solution doesn't need to be perfectly optimal but the smaller I can get it, the better.

# Answer
One standard approach for package managers these days seems to be to use a SAT solver (or ILP solver). That seems like a plausible solution. All of your requirements can be expressed in SAT (or ILP).

If you use SAT, you will need to constrain the number of packages selected, using a cardinality constraint: see Reduce the following problem to SAT (also Encoding 1-out-of-n constraint for SAT solvers has a few methods that can be generalized to this). Then, do binary search to find the minimal number of packages that can be selected. If you use ILP, see Express boolean logic operations in zero-one integer linear programming (ILP) for tips on expressing your constraints within ILP.

One approach to enforce 2-resolvability is to add a constraint for every pair of packages that they be simultaneously resolvable. However, a more efficient way might be to use lazy enforcement: initially, ignore those constraints, and solve the SAT/ILP instance without such a restriction. Then, check the resulting solution for any violations of 2-resolvability. For each pair of packages $P,Q$ that fail to be 2-resolvable with that solution, add a new constraint that $P,Q$ must be simultaneously resolvable, then solve the resulting modified SAT/ILP instance. Repeat until all such pairs are resolvable.

Another approach is to ask that there is a high probability that the set $\mathcal{S}$ of packages is simultaneously resolvable, where $\mathcal{S}$ is chosen according to some probability distribution that approximately mimics the packages a user is likely to ask to install. To achieve that, one approach would be to randomly sample $n$ such sets, $S\_1,\dots,S\_n$, from this distribution, then add constraints requiring that all of $S\_1,\dots,S\_n$ be simultaneously resolvable. Another variant of that is to add a constraint that requires that at least $0.9n$ of $S\_1,\dots,S\_n$ be simultaneously resolvable (using another cardinality constraint, if you are using SAT).
> 2 votes

---
Tags: graphs, optimization, satisfiability, constraint-satisfaction
---