# Question
Title: Does the use of True randomness work in this proof for P does not equal NP
To understand this proof you must first understand

1. NP vs P problem
2. The quantum eraser experiment
3. True randomness

Before we start I must first assert things that have been proven to be true, if you question any of my assertions feel free to research them yourself.

* True randomness does exist (demonstrated in quantum physics)
* True randomness by definition creates objective unpredictability
* Algorithms by definition can’t predict True randomness because it is objectively unpredictable (do not confuse with pseudo and statistical randomness which are predictable)
* If true randomness exists it is inherent that a 3SAT problem can be created using the true randomness (will create one just to avoid questioning)
* computers cannot create true randomness
* If True randomness is applied to a NP complete problem it will prove P does not equal NP (what this proof is going to explain)

P does not equal NP because Boolean satisfiability and 3SAT cannot be solved in polynomial time. To prove this we will create a 3SAT problem using True randomness, which cannot be predicted by a computer or a deterministic algorithm.

To create this problem we will use the quantum eraser experiment multiple times. For each potential variable we will have one slit, in this example we will have 12 slits for the 12 variables, 3 slits for the boolean operators, and an infinite amount of slits to determine the length of the problem (which will be defined as the number of clauses in the problem).

How the slits work in the context of this problem:

* Variables: we have 12 slits, whichever slit the photon goes through number 1-12 is the variable in that position, we run the experiment separate times for each variable position, the number of variables is determined by the length of the problem.
* Boolean operators: we have 3 slits, whichever slit the photon goes through number 1-3 is the operator in that position. We run the experiment separate times for each operator position, the number of operators is determined by the length of the problem.
* Length: an infinite amount of slits will be used to determine the length of the problem (which will be defined as the number of clauses in the problem). For example if the photon goes through slit 104 we will have 104 clauses in the problem.

The 3SAT blueprint would look like this if # shows a variable position, and ! shows an operator position.

```
(# ! # ! #) ! (# ! # ! #) ! (# ! # !#) etc

```

This is the pool of variables they can select from for the variable spots

```
(x1)
(x2)
(x3)
(x4)
(x5)
(x6)
(x7)
(x8)
(x9)
(x10)
(x11)
(x12)

```

This is the pool of Boolean operators that can be selected for the operator spots.

* The not operator (⇁)
* The and operator (∧)
* The or operator (∨)

I have now created a truly random problem, and by definition the result cannot be predicted. This assures that no math equation, function, or algorithm can be created to solve any of the problems we would generate as or more efficiently than a nondeterministic turing machine, meaning all of them would only be solvable in Nondeterministic Polynomial Time. They would only be solvable, because simply put we have assured that the only way to solve the problem is through brute force, in which a deterministic algorithm/turing machine cannot solve in polynomial time.

Finally P does not equal NP because true randomness by definition cannot be predicted by a deterministic algorithm, and therefore a deterministic turing machine would not be as efficient as a nondeterministic turing machine at solving a truly random 3SAT problem. Since we have created a 3SAT problem that is truly random in nature,(not pseudo random or statistically random). This means that we have finally proven that P cannot equal NP because the 3SAT problem we have created (an NP complete problem) cannot be solved in polynomial time, and a deterministic turing machine would be less efficient than a nondeterministic turing machine when solving it.

### Summary

We have proven P does not equal NP by creating a NP complete problem (3SAT) with true randomness, completely eliminating the ability for deterministic algorithms to predict results, making it so that no deterministic machine could solve it faster than a nondeterministic one. This also proves that it couldn't be solved in polynomial time, this finally proves P does not equal NP.

Here are things that might have been confusing in my argument, because I absolutely suck at showing a clear train of thought.

The objective of this is to eliminate all predictability in the problem, making brute force or “systematic” guessing the only way to solve it. We know this because by definition true randomness is unpredictable (NOT pseudo or statistical randomness we encounter in the real world which is predictable). There is no correlation between 2 problems generated by this formula, meaning if you solve one in nondeterministic polynomial time then find some strange supposed relationship between variables, that doesn’t give you the ability to solve another in polynomial time, because there truly is no relation between variables. The only deterministic algorithm will be systematically guessing which would not be more efficient than a nondeterministic turing machine.

here is the link https://www.academia.edu/110544358/Using\_True\_Randomness\_in\_Quantum\_Mechanics\_to\_Prove\_P\_Does\_Not\_Equal\_NP

# Answer
> 4 votes
I think you don’t quite understand what non-deterministic means.

Take the travelling salesman problem. Say 50 cities, and we ask if you can visit all of them and return to the start within 1950 miles. A nondeterministic algorithm guesses correctly in which order to visit the 50 cities, you add the distances, it’s less than 1950 miles, you are done. Very efficient except we can’t build a machine that does this.

(It’s not just guessing, you also need to prove that the guess is the correct solution. So if I guess the number of beans in a big glass correctly, I still need to count it to verify the guess).

# Answer
> 3 votes
It's a bit unclear how you make a leap from "The problem is truly random" to "the result can't be predicted".

Let's imagine another example: you use True Randomness to shuffle N numbers. Does this stop sorting algorithms from working? Obviously no, they will still work in O(N log N) time. So why does True Randomness make any difference in 3SAT if it doesn't matter in sorting?

# Answer
> 2 votes
It seems like you misunderstand what NP stands for and what the 3SAT problem is. NP stands for Nondeterministic Polynomial, which means that a non-deterministic Turing machine can guess a solution to the problem and determine the solution is correct in polynomial time ("Nondeterministic Polynomial Time", 2019). A problem in 3SAT is in Conjunctive Normal Form (CNF) of clauses Ci such as the following:

P = C1 ^ C2 ^ ... ^ Cn

Each clause is disjunctive with 3 arbitrary terms chosen from a set X such as the following Ci = (Xi ∨ ~Xj ∨ Xk)

Therefore, a sample instance of the 3SAT is the following.

P = (X4 ∨ X2 ∨ ~X3) ^ (X1 ∨ ~X2 ∨ X3)

Specifically, we want to know whether there is an assignment of truth values to the terms such that P is true (Kleinberg & Tardos, 2005).

The point I'm trying to make is that you can't choose arbitrary operators to generate random instances of the 3SAT problem, which brings me to my other point. You are attempting to simply generate random instances of the 3SAT problem, but when we discuss these algorithms, we are typically, already discussing arbitrary instances of the problem.

**References**

Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson.

*Nondeterministic Polynomial Time*. (2019). DeepAI. https://deepai.org/machine-learning-glossary-and-terms/nondeterministic-polynomial-time

---
Tags: complexity-theory
---


title: Should one test tests?

text:
# Question
Title: Should one test tests?
I study computer science and I was taught that sometimes one can test tests. The lecturer did not used citations. One other programmer told that this is not useful. Is there any research showing pros and cons of testing tests?

# Answer
My answer assumes you mean write automated tests for your automated tests.

In practice, this is not done. In fact, in the work place, people joke about testing the tests. However, if your tests utilize a modular piece of code that can use some testing, then write some unit tests for it. In this scenario, you are not really testing the tests, but you are testing a piece of code that is utilized in testing. So, no, don't test your tests because then you might need to write tests to test the tests that test your tests.

One obvious con about testing the tests is that you're wasting time writing more tests when time is already tight because you're in a 2 week sprint. Now, that you have tests to test the tests, you need to maintain that code too, so another con is created where you have to maintain your test code and maintain your tests that test the tests code, which just wastes more time.

**EDIT**

A software developer should not be testing tests. The tests are written to test the code the software developer is creating. The following will be useful for you:

https://softwareengineering.stackexchange.com/questions/11485/how-to-test-the-tests
> 1 votes

# Answer
In practice that happens as soon as the software you are testing is good enough (during development) that it should pass the test, and the test declares failure. At that point you know that software or test are faulty and find the fault.

And if I want to make sure your test detects faults in my software, then I will add a fault, check that the test fails, add a different fault etc. So as the software developer I may very well test your test.
> 0 votes

---
Tags: testing
---


# Question
Title: Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected
If a graph with $n$ vertices has more than $\frac{(n-1)(n-2)}{2}$ edges then it is connected.

I am a bit confused about this question, since I can always prove that for a graph to connected you need more than $|E|\>n-1$ edges.

# Answer
> 19 votes
I am not sure what bothers you but as I see it you are confused about the following two facts

1. If a graph is connected then $e \geq n-1.$
2. If a graph has more than $e \> \frac{(n-1)(n-2)}{2}$ then it is connected.

Notice that the implications in 1 and 2 are in opposite directions.

For a proof of 2. you can check out this link.

# Answer
> 7 votes
I think your problem might be to prove that you *cannot* construct an undirected graph with $\dfrac{(n-1)(n-2)}{2}$ edges that is not connected. You are thinking about it the wrong way. The $E = n - 1$ formula about how few edges can you use to connect all the vertices.

Imagine you are an adversary trying to design a horrible highway system so that one town is disconnected. No matter how inefficiently you spend your roads, you'll still have to connect all the towns if there are so many roads.

Consider what the worst possible design could be, eg, the one that uses as many roads as possible but still leaves one town disconnected. How many edges does that have? What happens when you add one more edge to that?

# Answer
> 4 votes
1.As you mentioned we have:

$G\text{ is connected} \Rightarrow |V|-1 \le |E|$

But the other direction is not true, i.e:

$G\text{ is connected} \Leftrightarrow |V|-1 \le |E|$

is wrong statement.

So you can not use it for further reasoning. Sample counter example is this graph ($K\_t$ is a complete graph on $t$ vertices, and $\cup$ means disjoint union of graphs):

$G = K\_{n-1} \cup K\_1$

$G$ has $n-1\choose 2$ edges and $n$ nodes, and ${n-1\choose 2} \> n-1$ for $n\>4$.

2.On the other hand, to prove that :

${|V|-1 \choose 2} \< |E| \Rightarrow G\text{ is connected}$

We can do it as follow:

Suppose not, then $G$ is disjoint union of two graphs $G=G\_1\cup G\_2$, with $|G\_1| = k, |G\_2| = n-k, 0\<k\<n$, if we connect all the vertices of $G\_1,G\_2$ together to make graph $G"$, then $|E\_{G"}|\le {n \choose 2}$ (because $G"$ has at most as complete graph edges) but:

${n-1 \choose 2} + 1 + k\cdot (n-k) \le |E\_{G"}| \le {n \choose 2} \Rightarrow$

$(k-1)(n-k-1) + 1 \le 0\Rightarrow$ Contradicts with $0\<k\<n$.

# Answer
> 0 votes
A simple graph with n vertices is connected if it has more than (n−1)(n−2)/2 edges.

The n vertex graph with the maximal number of edges that is still disconnected is a Kn−1

a complete graph Kn−1 with n−1 vertices has (n−1)/2edges, so (n−1)(n−2)/2 edges.

Adding any possible edge must connect the graph, so the minimum number of edges needed to guarantee connectivity for an n vertex graph is ((n−1)(n−2)/2) + 1

hence, a simple graph having 'n' number of vertices must be connected if it has more than (n−1)(n−2)/2 edges

# Answer
> 0 votes
Theorem: given a graph $G$ with $k$ components, the number of edges $m$ is inside the range $$ n - k \leq m \leq \frac{(n-k+1)(n-k)}{2} $$

You can find the proof of this theorem in Chapter 3 of "Graph Theory " by Robin J. Wilson. So I will skip the proof, if you need I will edit the answer.

If a graph has two components, it means that $k = 2$ and then it has a maximum of edges equal to $$ \frac{(n-1)(n-2)}{2} $$

If a graph has a higher number of edges, it means that $k=1$. Therefore the graph is connected.

# Answer
> -4 votes
Graph G has n nodes n=(n-1)+1 A graph to be disconnected there should be at least one isolated vertex.A graph with one isolated vertex has maximum of C(n-1,2) edges.

so every connected graph should have more than C(n-1,2) edges.

---
Tags: graphs
---


# Question
Title: Is the set of instances of PCP, which have a solution, semi-decidable?
My idea was that it is because we can construct a TM M' that simulates a TM M that is to find a solution for a PCP instance. M' accepts if M accepts, rejects if M rejects, and doesn't halt if M does not.

But I'm confused about the fact that in such a way we can also construct a TM M'' that simulates M. It rejects if M accepts and accepts if M rejects =\> the set of PCP instances that have no solution is semi-decidable.

The second set is a complement of the first one and they're both semi-decidable, which means that they're also decidable, so we can say when an instance has a solution (which is not the case, right?).

What am I missing?

Massive thanks for your explanations!

# Answer
You are essentially reasoning on the language $A\_{TM}$ rather than on $PCP$ instances. An algorithm such as the one you mention will show that $A\_{TM}$ (i.e. the language of pairs of Turing machines a words such that the Turing machine accepts the word) is a semi-decidable language. Now, the complement of $A\_{TM}$ is not even semidecidable. This is because this language consists of all pairs of Turing machines and words such that the Turing machine does not accept the word. In particular, this language contains those words for which the Turing machine does not halt, and you know that halting is undecidable. So I think in your reasoning above you were essentially missing the part on the negation of accepting being either rejecting or terminating.
> 0 votes

---
Tags: turing-machines, decision-problem, semi-decidability
---


# Question
Title: What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?
I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can you please share some examples or a URL link? Is the NP problem a semidecidable problem? If yes, then it means that NP-complete problems are Recursive enumerable. Please correct me if I am wrong.

I am thankful to you.

# Answer
> 0 votes
This is just equivalent to the class of RE problems (strictly RE\R). So one example would be finding whether a Diophantine equation has a solution.

* A program could "solve" this problem by iterating through all possible combinations of variables, and testing them. If a solution exists, the program halts and returns yes. If a solution doesn't, the program does not halt.

Here is a wikipedia link for more information: https://en.wikipedia.org/wiki/RE\_(complexity)

# Answer
> 0 votes
A problem in NP with the answer “yes” can be solved by getting a clever hint followed by a polynomial time verification.

We could solve it very very slowly by enumerating all possible hints.

Which means it is semidecidable, since solving the “yes” cases is enough to be semidecidable.

---
Tags: turing-machines, automata, np-complete, p-vs-np
---


# Question
Title: Find the smallest subarray with sum larger than a threshold
Given a set of $n$ positive numbers $\\{a\_1,\ldots,a\_n\\}$ and a positive target $T$, find a subset $S$ from $\\{a\_1,\ldots,a\_n\\}$ of contiguous elements, that is $S=\\{a\_i,a\_{i+1},a\_{i+2},\ldots\\}$ for some $i$, such that $|S|$ is minimum and $\sum\_{a\in S}a\geq T$.

My algorithm is an exhaustive search one.

* Generate all subsets of contiguous elements from $\\{a\_1,\ldots,a\_n\\}$.
* Start with the lowest-cardinality subset $S$ and check the constraint $\sum\_{a\in S}a\geq T$.

This gives $O(n^2)$ algorithm in the worst-case. Is there a better approach?

# Answer
> 6 votes
You can solve your problem in linear time using a "sliding window" algorithm.

Let $i,j$ be two pointers initialized to $1$, and denote by $\sigma(i,j)$ the sum $a\_i + a\_{i+1} + \dots + a\_{j}$. As long as $i \< n$ do the following:

* If $\sigma(i,j) \<T$ and $j\<n$, increment $j$ by $1$.
* Otherwise, increment $i$ by $1$.

Consider now all pairs of values $(i,j)$ attained by $i$ and $j$ during the previous procedure and, among those that satisfy $\sigma(i,j) \ge T$, return one that minimizes $j-i+1$.

Notice that the above algorithm can be implemented in time $O(n)$ since there are at most $2n-1$ considered pairs $(i,j)$ (each index can be incremented at most $n-1$ times) and you can update the value of $\sigma(i,j)$ in constant time whenever $i$ or $j$ changes (subtract $a\_{i}$ just before incrementing $i$, and add $a\_j$ immediately after incrementing $j$).

We only need to show that some pair considered $(i,j)$ corresponds to the endpoints $i^\*, j^\*$ of an optimal subarray $a\_{i^\*}, a\_{i^\*+1}, \dots, a\_{j^\*}$. At some point during the execution of the algorithm we must either have $i = i^\*$ or $j=j^\*$. Consider the first iteration when this happens.

* If $i=i^\*$ then $j \le j^\*$. Moreover, for all $j' \in \\{j, j+1, \dots, j^\*-1\\}$ (this set might be empty), we have $\sigma(i, j') \< T$ and hence $j$ gets incremented until $j=j^\*$ while $i$ remains unchanged. Therefore $(i^\*, j^\*)$ is considered.
* If $j=j^\*$ then $i \le i^\*$. Moreover, for all $i' \in \\{i, i+1,\dots, i^\*-1\\}$ (this set might be empty), we have $\sigma(i', j) \ge T$ and hence $i$ gets incremented until $i=i^\*$ while $j$ remains unchanged. Therefore $(i^\*, j^\*)$ is considered.

---
Tags: algorithms, subset-sum, maximum-subarray
---


# Question
Title: Results of a Program After Call By Reference Vs. Call By Value-Result
I have a question that I am trying to work through. I have a program:

```
1. program Pass
 2.   var b:integer; a:integer; v :array[5] of integer ;
 3.   procedure P (x:integer, y:integer ) ;
 4.     var z:integer ;
 5.     begin
 6.       z := x ;
 7.       x := y ;
 8.       y := z ;
 9.     end
10.   begin
11.     b := 1; a := 3; v := [ 2,1,4,5,4 ] ;
12.     P( a, v [ a ] ) ;
13.   end

```

And I am asked what are the values of `b, a` and `v` after call by reference and call by value-result. The array here also starts at index 1.

**Solution: Call By Reference**

For call by reference we learned that the actual parameters are aliased with the formal parameters (hopefully that wording is correct?) and actual parameters can be updated during execution of the code. For my solution I have:

1. alias a and x. a is set to 3;
2. alias v\[a = 3\] and y. v\[a = 3\] = 4 (indexing starts at one).
3. z = x = a = 3;
4. x = y = v\[a = 3\] = 4;
5. a is updated to 4;
6. v\[a = 4\] = y = z = 3;
7. v is \[2, 1, 4, 3, 4\].

So I have b = 1, a = 4; and v = \[2, 1, 4, 3, 4\], but the solution says v = \[2, 1, 3, 5, 4\]. Can someone help me understand why, if a is updated during the execution then why the solution has v\[3\] still being updated? I feel like I am missing a key piece of the mechanism here.

**Solution: Call By Value-Result**

For call by value-result we learned that parameters are copied in and then they are copied out after the code has executed. Here are the steps again that I took to solve the problem:

1. a = 3; passed into x; x = 3;
2. v\[a = 3\] = 4 (indexed by 1) and passed into y; y = v\[a = 3\] = 4;
3. z = x = 3;
4. x = y = 4;
5. y = z = 3;
6. x = 4 and y = 3 are copied out to a and v\[a\] which again is v\[a = 4\] now? I was told the answer below is correct but another question for me came up in what order are the values copied back? If v\[a\] was copied back first before a was changed then doesn't copy order play a role in how the values are updated?

So b = 1; a = 4; v = \[2, 1, 4, 3, 4\].

If anyone could help me sort out these thoughts I would greatly appreciate it.

# Answer
> 1 votes
Just to clean up some confusion: What you call “call by reference” was “call by name” in Algol. In newer languages, “call by reference” will take the address of an object and the function accesses the object through the reference. Call by value/result locates the object, passes a value, gets a value back and stores it in the same variable.

Swift has “auto closure” arguments that are passed as code that will be executed by the function allowing the same things as “call by name”.

In your first case you seem to evaluate what Algol “call by name” would do - the language also looks like Algol to me (distant memory). The solution you refer to would be a modern “call by reference” result, like you would get in C++.

In the second case, you are right, the result would be unspecified if v\[a\] was evaluated again. Most likely it would not.

---
Tags: terminology, programming-languages, semantics, evaluation-strategies
---


# Question
Title: Prime attribute dependant on another prime attribute allowed under BCNF?
I have been studying DBMS ans I have a question that I got conflicting answers to: Is prime attribute that is dependant on another prime attribute allowed under BCNF?

Meaning P-\>P.

I know that NP-\>P is not allowed. and also NP-\>NP (as it is not 3NF - transitive relation) Thanks.

# Answer
> 0 votes
By definition, a relation is in BCNF if and only if, for every non trivial functional dependency, the left hand part is a candidate key.

So, if you have a dependency `A → B` where both A and B are prime attributes, this dependency violates the Normal Form only if A is not a candidate key, but a part of some candidate key.

Note that in that case, the dependency does not violates the 3NF.

# Answer
> 0 votes
every determinant should be candidate key, so write down candidate keys, then write down functional dependencies. after that check whether on the left hand side of '-\>' what you have, if all of them are candidate keys(whole candidate keys, not part of it) then it is in BCNF, otherwise it violates BCNF property, where every determinant should be candidate key.

---
Tags: database-theory, databases
---


# Question
Title: How do I find time complexity of while loops?
I am designing a simple algorithm to be used at hardware level. And I want to find its time complexity.

```
i=1
while(i<=n)
{
    i=i*2;
}

```

# How I'd go about finding time complexity of this?(And I'm wrong).

i=1,2,4,8....n =$2^{n-1}$

So the time complexity is $2^n$

But I am wrong according to the professor. Why? Isn't my mathematics correct.

# Answer
The time complexity is dependent on the number of times the while loop loops. Since the value of i is increasing exponentially, the number of loops will be logarithmic.

* If the value of n=1, then the loop count = 1.
* If the value of n=2, then the loop count = 2.
* If the value of n=4, then the loop count = 3.
* If the value of n=8, then the loop count = 4.
* and so on

The pattern in general is that loop count = lg(n)+1, where "lg" is read "log base 2", which means that the asymptotic time complexity is O(lg(n))

See for yourself with the following python code snippet:

```
def main():
    i = 1
    loop_count = 0
    n=8

    while i <= n:
        i = 2*i
        loop_count = loop_count+1

    print("loop_count = " + str(loop_count) + " when n = " + str(n))

main()

```

As an exercise for yourself, can you determine the asymptotic time complexity if i is increasing by 3 * i; that is, i = 3 * i?
> 1 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem
I've come up with a greedy algorithm proof for the minimum denominations problem, and I'm curious if someone can verify the correctness of the proof for me. I have simplified the problem by restricting the denomination set to the US Coinage System. Thank you very much in advance.

**A Formal Definition of the Problem**

Given a set of denominations D = {.01, .05, .10, .25} and a number s, find an optimal solution set of denominations O such that the sum of its denominations is equal to s and given any other set of denominations C with the sum of its denominations equal to s, |O| \<= |C|. Note: we assume the set of denominations is the US coinage system because the greedy algorithm will work; however, the greedy algorithm will not always find the optimal solution given any generic denomination system.

**Mapping the Denominations**

Given the US Coinage system, we have the following statements that are true:

```
.01 = .01
.05 = .01 + .01 + .01 + .01 + .01
.10 = .05 + .05
.25 = .10 + .10 + .05

```

This means that all the denominations greater than .01 can be mapped or represented as the sum of lower denominations, which is an important property when proving the correctness of the algorithm.

**Designing a Greedy Algorithm for the Problem**

Let the variable a (short for accumulator) be the current sum of the denominations of the optimal set O we are seeking, which is initialized to zero. To greedily solve this problem, at each step of the algorithm we can choose the largest denomination D\[i\] such that a + D\[i\] \< s and add d\_i to the set O. That’s the greedy algorithm. Now, we can create some pseudo code for the algorithm to solve the problem.

```
Proc Min-Denominations(D, s)
    O = {}
    I = |D|
    a = 0

    While a < s and i >= 0
        While a+D[i] <= s
            a = a + D[i]
            O = O U {D[i]}
        End While
        i = i - 1
    End While

    Return O
End Proc

```

Note: It’s important to note that this algorithm assumes that the set of denominations is sorted.

**Proving Min-Denominations Finds the Optimal Solution**

To prove the greedy algorithm finds the optimal solution, we will use a method known as an exchange argument, which is a powerful way to think about greedy algorithms in general. The exchange argument works by gradually modifying the optimal set O, such that optimality is preserved at each step and transforming it into the optimal set discovered by the greedy algorithm (Kleinberg & Tardos, 2005).

A nonoptimal property for the problem at hand is what I call a denomination expansion, which is a term created for reasoning about this problem. A nonoptimal set O’ with a denomination expansion has a subset C such that the sum of the denominations in C is equal to a denomination di = c1+c2+...+cq.

**A. All sets of change with no denomination expansions have the same number of denominations.**

By contradiction, assume that A and B are two sets of change such that there are no denomination expansions and |A| = n and |B| = m and n \> m. This means the following:

S = a1 + a2 + … + an = b1 + b2 + … + bm

Since n \> m, there must be a denomination bi in B and a subset of A called C where |C|=q such that bi = c1 + c2 + … cq. This is by definition a denomination expansion, which contradicts the assertion that A and B are two sets without any denomination expansions.

**B. There is an optimal set of denominations that has no denomination expansions.**

**B1. If O has a denomination expansion, then there is a subset C of O and a denomination d such that d = c1 + c2 + … + cq.**

Consider a denomination expansion in O, by definition of denomination expansion, there is a subset C of O such that d = c1 + c2 + … + cq, which means there are q-1 more denominations than necessary.

Now suppose O has at least one denomination expansion, and let it be defined as in (B1) where d = c1 + c2 + … + cq. Now, let’s exchange the denominations c1, c2, …, cq with the denomination d. After the exchange, we can see there is one less denomination expansion O and no new expansions were created. Therefore we have that

**B2. After exchanging the denominations we have a change amount with q-1 less denominations such that |O| = n - (q-1)**

**B3. The new exchanged set of denominations has no more denominations than O when all denomination expansions are removed.**

This proof is similar to (A). By contradiction, assume A has no denomination expansions and O is the optimal set of denominations such that |A| = n and |O| = m and m \< n since the optimal set must by definition have the least amount of denominations. Also, assume that a1+a2+...+an = o1 + o2 + … + om = s. This implies there is a subset C of A and a denomination oi in O such that oi = c1 + c2 + … + cq. By definition, there is a denomination expansion in A, which contradicts the assertion that A has no denomination expansions.

The optimality of our greedy algorithm now follows immediately.

**C. The change produced by Min-Denominations is the optimal minimum number of denominations.**

Statement B proves that an optimal set of change has no denomination expansions, and our greedy algorithm produces a set of denominations with no denomination expansions. Statement A shows that any pair of sets of change with no denomination expansions have the same amount of denominations. Therefore, the change obtained by running our greedy algorithm is optimal.

**References**

Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson.

**EDIT** I added the mapping the denominations section to improve clarity of the correctness of the proof.

# Answer
I decided to write a python script that generates all the optimal solutions for all the change. You can literally scroll through the solutions and observe there are no denomination expansions. So, my proof is indubitably correct at this point.

```
If change is 2, then the optimal solution is: [1, 1]
If change is 3, then the optimal solution is: [1, 1, 1]
If change is 4, then the optimal solution is: [1, 1, 1, 1]
If change is 6, then the optimal solution is: [5, 1]
If change is 7, then the optimal solution is: [5, 1, 1]
If change is 8, then the optimal solution is: [5, 1, 1, 1]
If change is 9, then the optimal solution is: [5, 1, 1, 1, 1]
If change is 11, then the optimal solution is: [10, 1]
If change is 12, then the optimal solution is: [10, 1, 1]
If change is 13, then the optimal solution is: [10, 1, 1, 1]
If change is 14, then the optimal solution is: [10, 1, 1, 1, 1]
If change is 15, then the optimal solution is: [10, 5]
If change is 16, then the optimal solution is: [10, 5, 1]
If change is 17, then the optimal solution is: [10, 5, 1, 1]
If change is 18, then the optimal solution is: [10, 5, 1, 1, 1]
If change is 19, then the optimal solution is: [10, 5, 1, 1, 1, 1]
If change is 20, then the optimal solution is: [10, 10]
If change is 21, then the optimal solution is: [10, 10, 1]
If change is 22, then the optimal solution is: [10, 10, 1, 1]
If change is 23, then the optimal solution is: [10, 10, 1, 1, 1]
If change is 24, then the optimal solution is: [10, 10, 1, 1, 1, 1]
If change is 26, then the optimal solution is: [25, 1]
If change is 27, then the optimal solution is: [25, 1, 1]
If change is 28, then the optimal solution is: [25, 1, 1, 1]
If change is 29, then the optimal solution is: [25, 1, 1, 1, 1]
If change is 30, then the optimal solution is: [25, 5]
If change is 31, then the optimal solution is: [25, 5, 1]
If change is 32, then the optimal solution is: [25, 5, 1, 1]
If change is 33, then the optimal solution is: [25, 5, 1, 1, 1]
If change is 34, then the optimal solution is: [25, 5, 1, 1, 1, 1]
If change is 35, then the optimal solution is: [25, 10]
If change is 36, then the optimal solution is: [25, 10, 1]
If change is 37, then the optimal solution is: [25, 10, 1, 1]
If change is 38, then the optimal solution is: [25, 10, 1, 1, 1]
If change is 39, then the optimal solution is: [25, 10, 1, 1, 1, 1]
If change is 40, then the optimal solution is: [25, 10, 5]
If change is 41, then the optimal solution is: [25, 10, 5, 1]
If change is 42, then the optimal solution is: [25, 10, 5, 1, 1]
If change is 43, then the optimal solution is: [25, 10, 5, 1, 1, 1]
If change is 44, then the optimal solution is: [25, 10, 5, 1, 1, 1, 1]
If change is 45, then the optimal solution is: [25, 10, 10]
If change is 46, then the optimal solution is: [25, 10, 10, 1]
If change is 47, then the optimal solution is: [25, 10, 10, 1, 1]
If change is 48, then the optimal solution is: [25, 10, 10, 1, 1, 1]
If change is 49, then the optimal solution is: [25, 10, 10, 1, 1, 1, 1]
If change is 50, then the optimal solution is: [25, 25]
If change is 51, then the optimal solution is: [25, 25, 1]
If change is 52, then the optimal solution is: [25, 25, 1, 1]
If change is 53, then the optimal solution is: [25, 25, 1, 1, 1]
If change is 54, then the optimal solution is: [25, 25, 1, 1, 1, 1]
If change is 55, then the optimal solution is: [25, 25, 5]
If change is 56, then the optimal solution is: [25, 25, 5, 1]
If change is 57, then the optimal solution is: [25, 25, 5, 1, 1]
If change is 58, then the optimal solution is: [25, 25, 5, 1, 1, 1]
If change is 59, then the optimal solution is: [25, 25, 5, 1, 1, 1, 1]
If change is 60, then the optimal solution is: [25, 25, 10]
If change is 61, then the optimal solution is: [25, 25, 10, 1]
If change is 62, then the optimal solution is: [25, 25, 10, 1, 1]
If change is 63, then the optimal solution is: [25, 25, 10, 1, 1, 1]
If change is 64, then the optimal solution is: [25, 25, 10, 1, 1, 1, 1]
If change is 65, then the optimal solution is: [25, 25, 10, 5]
If change is 66, then the optimal solution is: [25, 25, 10, 5, 1]
If change is 67, then the optimal solution is: [25, 25, 10, 5, 1, 1]
If change is 68, then the optimal solution is: [25, 25, 10, 5, 1, 1, 1]
If change is 69, then the optimal solution is: [25, 25, 10, 5, 1, 1, 1, 1]
If change is 70, then the optimal solution is: [25, 25, 10, 10]
If change is 71, then the optimal solution is: [25, 25, 10, 10, 1]
If change is 72, then the optimal solution is: [25, 25, 10, 10, 1, 1]
If change is 73, then the optimal solution is: [25, 25, 10, 10, 1, 1, 1]
If change is 74, then the optimal solution is: [25, 25, 10, 10, 1, 1, 1, 1]
If change is 75, then the optimal solution is: [25, 25, 25]
If change is 76, then the optimal solution is: [25, 25, 25, 1]
If change is 77, then the optimal solution is: [25, 25, 25, 1, 1]
If change is 78, then the optimal solution is: [25, 25, 25, 1, 1, 1]
If change is 79, then the optimal solution is: [25, 25, 25, 1, 1, 1, 1]
If change is 80, then the optimal solution is: [25, 25, 25, 5]
If change is 81, then the optimal solution is: [25, 25, 25, 5, 1]
If change is 82, then the optimal solution is: [25, 25, 25, 5, 1, 1]
If change is 83, then the optimal solution is: [25, 25, 25, 5, 1, 1, 1]
If change is 84, then the optimal solution is: [25, 25, 25, 5, 1, 1, 1, 1]
If change is 85, then the optimal solution is: [25, 25, 25, 10]
If change is 86, then the optimal solution is: [25, 25, 25, 10, 1]
If change is 87, then the optimal solution is: [25, 25, 25, 10, 1, 1]
If change is 88, then the optimal solution is: [25, 25, 25, 10, 1, 1, 1]
If change is 89, then the optimal solution is: [25, 25, 25, 10, 1, 1, 1, 1]
If change is 90, then the optimal solution is: [25, 25, 25, 10, 5]
If change is 91, then the optimal solution is: [25, 25, 25, 10, 5, 1]
If change is 92, then the optimal solution is: [25, 25, 25, 10, 5, 1, 1]
If change is 93, then the optimal solution is: [25, 25, 25, 10, 5, 1, 1, 1]
If change is 94, then the optimal solution is: [25, 25, 25, 10, 5, 1, 1, 1, 1]
If change is 95, then the optimal solution is: [25, 25, 25, 10, 10]
If change is 96, then the optimal solution is: [25, 25, 25, 10, 10, 1]
If change is 97, then the optimal solution is: [25, 25, 25, 10, 10, 1, 1]
If change is 98, then the optimal solution is: [25, 25, 25, 10, 10, 1, 1, 1]
If change is 99, then the optimal solution is: [25, 25, 25, 10, 10, 1, 1, 1, 1]

```
> 1 votes

# Answer
The greedy algorithm is optimal if it only picks 1c coins. It is optimal if it picks a 5c coin as the highest because the alternative is five 1c. It is optimal if it picks one or two 10c because the alternative is two or four 5c. And it is optimal if it picks 25c coins because the alternative is two 10c and replacing one 5c with 10c.

If you had 1c, 9c and 10c then greedy would be non-optimal for 18c. Would be interesting to find an algorithm that finds whether for a combination of coins greedy is not always optimal.

PS. From a different question: Given a set of coins, to check whether the greedy algorithm is always optimal, you only need to check that the greedy algorithm will use at most two coins for any sum of two coins.

Given coins $c\_i$, take every pair $i \le j$, and find the largest k such that $c\_k \le c\_i + c\_j$. If $k \ne j$ and $c\_k \ne c\_i + c\_j$ and there is no coin equal to $c\_i + c\_j - c\_k$ then greedy is not always optimal. It follows that greedy is optimal whenever each coin is at least twice the size of the previous one.
> 1 votes

---
Tags: algorithms, proof-techniques, greedy-algorithms, correctness-proof
---


# Question
Title: Find the value of return variable based on the value of n?
```
function fun(n) {
  let i,
    j,
    p,
    q = 0;
  for (i = 1; i <= n; ++i) {
    p = 0;
    for (j = n; j > 1; j = j / 2) {
      ++p;
    }
    for (k = 1; k < p; k = k * 2) {
      ++q;
    }
  }
  return q;
}

let val_q = fun(36);
console.log(val_q);

```

My confusion:

1. Outer loop runs $n$ times.
2. The loop with $j$ will run this many times:

Assume $n=32$ Then $j=32,16,8,4,2,1$

Let us generalize.

```
For p=1, j=32
For p=2, j=16
For p=3, j=8
For p=4, j=4
For p=5, j=2
For p=6, j=1

```

I assume from my basic mathematics, $p=n\cdot(\frac{1}{2})^{p-1}$

I can't solve this to find the $O(p)$ in terms of $n$.

3. For the loop with $k$, here's what my thought process is:

Doing similar stuffs, we get

```
For q=1, k=1
For q=2, k=2
For q=3,k=8

```

And so on. We can generalize that:

$k=2^q$

We also have:

$k\<p$ That means if we put all the values of k and p, we get: $q=\log\_2(n)+1-p$

BUT Finally: We can write: Value of $q=n\cdot \log\_2(n)+1-p$

This is the best I can do. :D

# Answer
> 1 votes
1. The outer loop runs $n$ times.
2. The first inner loop (the loop in $j$) runs approximately $\log\_2 n$ times. This is because it runs until, by dividing $n$ by $2$, we obtain a number $\leq 1$. This means that it runs $m$ times, where $m$ is the smallest integer such that: $\frac{n}{2^m}\leq 1$. This happens when $n \leq 2^m$, i.e. $m \geq \log\_2 n$ (the logarithm is a monotonic increasing function, so we can "apply it to inequalities"). More precisely, since we require $m$ to be integer, $m$ will be $\lceil \log\_2 n \rceil$, i.e. the integer superior part of $\log\_2 n$. Actually, if we want to be more precise, the first inner loop works with an integer index $j$, but each time we divide by $2$ this is not guaranteed (unless $n$ is a power of $2$). This means that from cycle to cycle we can have several roundings. For instance, if $n=15$, the values of $j$ will be $15, 7, 3, 1$, so the loop will run $3$ times instead of $4$. This leads us to a number of runs of $\lfloor \log\_2 n \rfloor$ (i.e. the integer part of $\log\_2 n$). Thus $p$ will be $\lfloor \log\_2 n \rfloor$.
3. The second inner loop (that in $k$) do the same thing as the loop in $j$, but it starts from $1$ and goes up (so we don't have the rounding problems and we use the integer superior part $\lceil \cdot \rceil$). The calculations are the same and we get an increment in $q$ of $\lceil \log\_2 p \rceil$ at each iteration of the outer loop.

Summing up, for $n$ runs of the outer loop, we get: $$q=n\cdot\left(\bigl\lceil \log\_2 \lfloor \log\_2 n \rfloor \bigr\rceil\right) \ .$$

Note that $p$ is reset at each iteration of the outer loop while $q$ is not.

The asymptotic time complexity is thus: $O(n\log n))$ because the most expensive operation inside the outer loop is the loop in $j$ which runs $O(\log n)$ times, while the loop in $k$ is a lower-order term.

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Is bytecode ("virtual machine code") inherently faster to compile and/or interpret, than higher level (above Assembly) languages?
First, this is not an opinion question. I'm interested in if there is some kind of objective answer. If there isn't, then the answer would be "no".

Is bytecode ("virtual machine code" for a "virtual processor") inherently faster to compile and/or interpret, than higher level (above Assembly) languages? What I mean is, does the bytecode map to the machine instructions of the underlying processor more easily than some higher level language? Why I ask is, it doesn't seem entirely certain to me that it does.

# Answer
> 4 votes
> does the bytecode map to the machine instructions of the underlying processor more easily than some higher level language?

That depends entirely on the bytecode, the higher level language, and the machine instructions.

For example, *Haskell* semantics map closely to the *Reduceron* CPU, whereas *JVM bytecode* semantics do not.

*ESPOL* semantics map closely to the *B5000*, whereas *CLI CIL* semantics do not.

*C* semantics map better to *AMD64* than *JVM bytecode* does, but *JVM bytecode* semantics map better to *picoJava* than C does – in fact, JVM bytecode *is* picoJava's machine code.

For every pair of high level language and bytecode, one can design a CPU that performs horrible for one or the other.

---
Tags: compilers, interpreters
---


# Question
Title: How to compute the complexity of $T(n) = 2T(\frac{n}{2}) +O(n\log n)$
I'm trying to solve the recurrent $$T(n) = 2T\left(\frac{n}{2} \right) +O(n\log n)$$

I thought about Master's theorem but unfortunately, my recurrent doesn't belong to any cases

Could you please help me with solving my difficulties? Thank you a lot for your help.

# Answer
> 1 votes
It does not make sense to talk about the **complexity** of a recurrence equation. Algorithms have complexities (sometimes expressed via recurrence equations). Recurrences have solutions.

Anyway, your recurrence is covered by the second case of the master theorem formulation you posted. More precisely, if $T(n) = a T(n/b) + f(n)$ where $f(n) = \Theta(n^{\log\_b a} \log^k n)$ for some $k \> -1$, then $T$ has solution $T(n) = \Theta(n^{\log\_b a} \log^{k+1} n)$.

In your specific case $a=b=2$ and $k=1$, therefore the solution is $T(n)=O(n \log^2 n)$.

# Answer
> 1 votes
Consider $n = 2^k$ and then expand the recurrence.

$\displaystyle T(n) = 2T(\frac{n}{2}) + O(nlog(n)) = O(k2^k + 2(k-1)2^{k-1} + 2^2T(2^{k-2})) = O(\sum^{k}\_{i = 0} 2^{i} (k-i) 2^{k-i}) = O(2^k \sum^{k}\_{i=0} (k-i)) = O(k^2 2^k) = O(nlog^2(n))$

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


# Question
Title: Why Is Inverse Quantization and Inverse Transform Taken Before Motion Estimation in H.264?
Here is the block diagram of the pipeline for the H.264 encoder (*Fundamentals of Multimedia by Ze-Nian Li, Mark S. Drew and Jiangchuan Liu*).

The feedback loop is used for motion estimation, but why is it taken **after** the transform and quantization steps? Why introduce and overhead from the inverse functions?

I know there's likely a very good reason for it, and this might sound like a stupid question, but I'd appreciate any answer that nudges me in the right direction.

Thanks!

# Answer
Inverse quantization and inverse transform are how the encoder keeps track of which pixel-values the decoder will have in its buffer at any give point in time. If you skip that step, then you make the encoder a tiny bit faster, but the resulting compressed video will be much lower quality.

---

Let $S\_i$ be the sequence of source/input frames. Let $\Delta\_i$ be the lossy-compressed difference between each frame and the previous. Let $O\_i$ be the decoded/output frames. Let $Q\_i$ be the quantization noise. And for simplicity assume that the motion vectors are all zero.

In the normal encoder workflow, the encoder tries to set $\Delta\_i = S\_i - O\_{i-1}$; but it can't do so exactly due to quantization; so it actually ends up with $\Delta\_i = S\_i - O\_{i-1} + Q\_i$.

The decoder adds up the deltas, and gets $O\_i = O\_{i-1} + \Delta\_i = S\_i + Q\_i$. In particular, the difference between an output frame and the corresponding input frame is at most 1 quantizer unit, as it should be.

---

Now consider your proposed change to the encoder workflow. The encoder tries to set $\Delta\_i = S\_i - S\_{i-1}$; but it can't do so exactly due to quantization; so it actually ends up with $\Delta\_i = S\_i - S\_{i-1} + Q\_i$. The encoder doesn't try to measure the value of $Q$ or adjust any future decisions to compensate, but quantization noise is still affecting the output frame just as much as before.

The decoder gets $O\_1 = O\_0 + \Delta\_1 = S\_1 + Q\_1$; $O\_2 = O\_1 + \Delta\_2 = S\_2 + Q\_1 + Q\_2$; $O\_i = S\_i + \Sigma\_{j=1}^i Q\_j$. Each output frame is farther and farther from the corresponding input frame as time goes on. (Until the it's reset by an intra-frame, but those can be hundreds of frames apart, so that's still a lot of time to accumulate error.)

If we assume that quantization noise is uncorrelated, then the rate-of-growth of the error would be about $\sqrt i$ by the Law Of Large Numbers. If we make more realistic assumptions where noise can be correlated then it's even worse and might grow as fast as linear.

---

To be more concrete and worst-case, suppose we have a video that starts with an all-black frame (i.e. luma=0), and slowly fades to white (luma=255) over the course of the next 255 frames, at a rate of +1 luma per frame. And suppose the quantizer is 2.

The standard encoder records a delta whenever the next input frame differs from the previous encoded frame by 1 quantizer (i.e. +2 luma in this case). The result is a fade-in of +2 luma every 2 frames. Not quite as smooth as the input video, but basically matches the intended scene.

Your proposed encoder would look at each input frame; see that it's only 1 luma of difference from the previous frame, which is smaller than the quantizer and thus rounds to 0; so you'd fail to record any change at all. The end of the scene would still be showing black when it should be white.
> 2 votes

---
Tags: video
---


# Question
Title: Why can't humans translate all of their abilities into an algorithm? Will that hold true in the future?
I know that an algorithm can't decide whether another algorithm halts on an input or not (a Turing machine can't decide whether another Turing machine will halt on an input). But I, as an human, can: I mean you just don't end up in your activity as a programmer with a looping algorithm and you don't know why!

To do this, you generally analyze the (somewhat) natual language of the code you wrote. Considering this, it comes to no surprise to me that for a machine this is hard to do: if I had to write a convicing chatbot (also a problem in the realm of natural language) in a programming language with traditional techniques it would turn out to be pretty bad. But why is that? Is there any term or concept that clearly differentiates between what humans are able to do, what machines are able to do and why is there exists this distinction?

Also, it seems to me that with advacements in artificial intelligence developement it won't be long until a machine will be able to carry out the aforementioned tasks (in particular loop detection). How does that relate to our traditional computability model? I mean artificial intelligence is still powered by algorithms, does't that violate it?

# Answer
Your question contains so many sub-questions and claims, making it really hard to answer, but I will try my best, starting with debunking your claims.

## No, You Cannot Predict Halting!

You are conflating loop detection with the halting problem. Loops are only the very simplest type of recursion. Modern code analysis can already detect most kinds of infinite loops. But those are trivial in the grander scheme of the halting problem. I really encourage you to read Alan Turing's original proof of the halting problem. It is simple and really clever. It does not matter what kind of smart Turing machine "oracle" program You write. Alan Turing would wrap it in another program whose halting cannot be predicted by that "oracle", i.e. it's not an oracle!. "AI" running on Turing machines is not able to escape the halting problem.

You, as a human being, cannot predict halting of a Turing program either! Consider the following program:

```
while(true) {
  compute more digits of pi;

  if( computed digits of pi contain the ASCII-encoded text of the bible )
    halt;
  else
    continue;
}

```

Does this problem halt? Mathematicians believe that it does, but they do not seem to know. If you can predict the halting of this problem, you have just given a new mathematical proof. And while You're at it , you could also easily prove Goldbach's conjecture.

In order to appreciate, just how long the runtime of a finite Turing program can be, you should look into the Busy Beaver Numbers. Astronomical does not even begin to describe these numbers...

## Why Can't humans Translate All of their Abilities Into Algorithms?

Now let's get to the core question. When teaching a human ability to a machine, I see the following two key requirements/challenges:

1. You must be sufficiently aware of how the ability works
2. You must be able to describe that ability to a computer

On a basic level, computers work on binary numbers, arithmetic and logic. The field of mathematics is one that we humans very consciously developed. So it comes as no surprise that mathematical problems, like linear equation systems, were the first to be solved by a computer.

In the years since, we have become better and better at solving challenge #2. We have developed better and better programming languages, input devices, editors and design tools to better teach/tell a computer what to do.

Challenge #1, however, is almost unsolvable. There are so many things that we humans do without thinking about them. They are encoded into our genes, and/or learned subconsciously. It is incredibly hard to describe how we do these things. How do we detect objects in 3-dimensional space? How do we compare images? How do we identify noises and percieve languages? How do we walk? How do we grab things and pass them to other people? How do we feel empathy, sympathy, apathy and antipathy for other people? How do we feel, emit and perceive emotions?

## Will "AI" Help?

Yes and no! "AI" will certainly help us with challenge #2 by enabling all kinds of new human-machine interfaces. Telling our computer what we want to achieve will become much simpler than typing in rigid code.

It is not so clear, however, if "AI" will help us solving challenge #1. Sure, we can teach a machine how to detect an object in an image already, or how to summarize text and answer questions. But that does not mean, we have taught human abilities to the machine. We have taught it to *imitate* human abilities. It's an important distinction, I would argue. It's like a Psychopath, practicing how to cry in front of a mirror and learning simple rules about when to cry. It may look like grief, but it isn't.

There's one way I can see how current "AI" could help us with translating more human abilities into machine code: "AI" could help us improve our understanding of neurobiology.

You may argue that imitating human abilities is good enough. In that case, we are making a lot of progress already and will continue to do so in the near future, thanks to machine learning. There are, however, a lot of challenges. The training data, for example, may not be entirely representative of human behavior. Text data is notoriously bad at conveying tone and emotions, especially the short form, attention driven text posted on internet platforms. The physical distance and anonymity provided by the internet also promotes apathy. Narcissists may produce a lot more text on the internet than mentally sane people. On top of that generative "AI" will soon flood the internet with spam indistinguishable from human spam. If this text data is used for training machine learning models, it will create a distorted imitation of human behavior.
> 3 votes

---
Tags: turing-machines, computability, artificial-intelligence, philosophy
---


# Question
Title: Polynomial Hierarchy - the difference between $\Pi$ and $\Sigma$
The way I understand is that complexity classes which are denoted with $\Sigma\_i$ are representing a combination of alternating variable quantifiers which must start with an existential quantifier $\exists$, for example: $\exists y\_1 \forall y\_2 ... Q y\_i$ and the last quantifier does not really matter. That is why we can say that $\Sigma\_1 P \subseteq \Sigma\_2 P$ because the last quantifier can act as a dummy quantifier.

However, what bothers me in my understanding is the example when we say that $\Pi\_1 P \subseteq \Sigma\_2 P$. In my understanding the variables $y$ are ordered and hence in $\Pi\_1 P$ we state that this is true for every $y\_1$ whereas in $\Sigma\_2 P$ we state that this is true only for some $y\_1$ which is much less restrictive.

By any chance, is my reasoning that $y$ variables are ordered false? In that case I would understand that we can just add a dummy quantifier up front just like we did in the first example.

# Answer
Your conception of the variable ordering is misleading you, and we can indeed add a dummy variable at the beginning.

If we have a $\Pi\_1\mathrm{P}$-problem $S$, we can write it as $S(x) \Leftrightarrow \forall y\_1 Q(x,y\_1)$. But then of course we also have that $S(x) \Leftrightarrow \exists y\_1 \forall y\_2 \ Q(x,y\_2)$, and thus conclude that $S \in \Sigma\_2\mathrm{P}$.
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: number of edges that appeared at least in one shortest path
In a simple weighted graph, with n vertices and m edges , for each pair of vertices we want to find the number of edges that appeared at least in one of the shortest paths between these two vertices.

I assume we can solve it using Floyd-Warshall algorithm or something similar to it but I tried and didn't reach any algorithm. I think its complexity should be O(N^3)

# Answer
The following is a naive algorithm:

1. Run Floyd-Warshall algorithm. It will give the shortest path values $d(s,t)$ between every pair of vertices $s, t \in V$.
2. For each edge $(u,v)$ and pair of vertices $s$ and $t$, if $d(s,u) + d(u,v) + d(v,t)= d(s,t)$, means there exists a shortest path from $s$ to $t$ via edge $(u,v)$.

In this way, you can compute the number of edges that appeared in at least in one of the shortest paths between any two vertices. The running time of the step $1$, is $O(|V|^3)$ and step $2$ is $O(|E| \cdot |V|^2)$. Therefore, the overall running time is $O((|E|+|V|) \cdot |V|^2)$.
> 1 votes

---
Tags: graphs, graph-traversal, weighted-graphs
---


# Question
Title: Hash function that returns the same result when the input is reversed
Do any hash functions exist that provide the same result if the input is reversed?

If this is impossible, why is it impossible?

I am interested in sending packets of constant size around a circuit in a network in both directions, having each node add its value to the hash and then, when the packets meet, compare the hash values.

# Answer
You could take any hash function $H$ and define a new hash function $H'$ as $H'(x) = H(x \Vert x^R)$, where $\Vert$ denotes concatenation and $x^R$ is the reversed version of $x$.
> 2 votes

---
Tags: algorithms, hash, hashing
---


title: Reversible streaming hash function

text:
# Question
Title: Reversible streaming hash function
Do any streaming hash functions exist that provide the same result if the input is reversed?

That is to say, is there some hash function, $h$, such that:

$$ h(h(h(h(0, x\_1), x\_2), ...), x\_n) = h(h(h(h(0, x\_n), ...), x\_2), x\_1) $$

If this is impossible, why is it impossible?

I am interested in sending packets of constant size around a circuit in a network in both directions, having each node add its value to the hash and then, when the packets meet, compare the hash values.

# Answer
> 3 votes
As stated, the problem is impossible (with a non-trivial hash function). Consider the case n=2, then you have that, for example,

$$h(h(0, 1), 2) = h(h(0, 2), 1)$$

That implies that

$$h(h(h(0, 1), 2), 3) = h(h(h(0, 2), 1), 3)$$

So the strings $1,2,3$ and $2,1,3$ are forced to have the same hash even if one is not the reverse of the other. A similar argument shows that any such hash function is not only reversal-independent, but in general permutation-independent, so it is equivalent to storing the multiset of characters of the input.

An alternative is to have a normal streaming hash function $h$ which is not reversal-independent, and then have a function $r$ that identifies the hashes of a string and its reverse. So the condition would become something like

$$ r(ℎ(ℎ(ℎ(ℎ(0,\_1),\_2),...),\_))=r(ℎ(ℎ(ℎ(ℎ(0,\_),...),\_2),\_1)) $$

And that is certainly possible with a reasonably strong hash function, as show by D.W.

# Answer
> 3 votes
There are several polynomial-based hash functions $H$, where you can rapidly compute $H(m)$ or $H(\text{rev}(m))$ given $m$, and you can do both in a streaming fashion. See below for several candidates for $H$. Then, you can use

$$H'(m) = H(m) \oplus H(\text{rev}(m)),$$

and $H'$ will have the property you are looking for.

# Rabin hash

For instance, consider the Rabin hash. Specifically, given a $n$-bit message $m=(m\_0,\dots,m\_{n-1})$, the hash is

$$H(m) = m\_0 + m\_1 x + \dots + m\_{n-1} x^{n-1} \bmod p(x),$$

where $p(x)$ is an irreducible polynomial of degree $k$ over $GF(2)$. This is easy to compute in a streaming fashion via the recurrence

$$w\_i = x w\_{i-1} \bmod p(x), \qquad h\_i = h\_{i-1} + m\_i w\_i \bmod p(x).$$

Now $\text{rev}(m)=(m\_{n-1},\dots,m\_1,m\_0)$, so

$$H(\text{rev}(x)) = m\_{n-1} + m\_{n-2} x + \dots + m\_0 x^{n-1} \bmod p(x),$$

which can be computed in a streaming fashion with the recurrence

$$h\_i = x h\_{i-1} + m\_i \bmod p(x).$$

# Polynomial hash over the integers

A related scheme is to use the integers modulo $p$ (a prime). instead of the polynomials over $GF(2)$ modulo $p(x)$. Specifically, given a $n$-bit message $m=(m\_0,\dots,m\_{n-1})$, the hash is

$$H(m) = m\_0 + m\_1 a + \dots + m\_{n-1} a^{n-1} \bmod p,$$

where $p$ is a prime number and $1\<a\<p$. This too can be computed in a streaming fashion, both for the message and for the reverse of the message, in the same manner as above. This can be made more efficient by breaking $m$ down into $n$ chunks, with each chunk of $c$ bits, such that $2^n\<p$, and let $m\_i$ be the $i$th chunk of $m$. For instance, each chunk might represent a byte or character of $m$.

Note that if you use chunks larger than a bit, then this assumes reversal means not "reversal as a bit-string" but "reversal as a sequence of characters". If you want one notion of reversal, but a different granularity for computing the hash, this can be arranged by with a little bit of additional arithmetic, but it's probably not worth the bother to work out the equations.

# Buzhash

Another choice for $H$ is Buzhash. Let $h$ be some hash function that maps from characters to $k$-bit values. Define $\oplus$ to represent xor, and $a \lll b$ to represent circular left-rotate of $a$ by $b$ bit positions (I will assume that $b$ is implicitly taken modulo $l$). Given a $n$-character message $m=(m\_0,\dots,m\_{n-1})$, Buzhash is defined as

$$H(m) = (h(m\_0) \lll n-1) \oplus (h(m\_1) \lll n-2) \oplus \cdots \oplus (h(m\_{n-2}) \lll 1) \oplus m\_{n-1}.$$

This can be easily computed in a streaming fashion by

$$h\_i = (h\_{i-1} \lll 1) \oplus h(m\_i).$$

Also $H(\text{rev}(m))$ can be easily computed in a streaming fashion by

$$h\_i = h\_{i-1} \oplus (m\_i \lll i).$$

The same comments apply about the granularity of chunks.

---
Tags: hash, cryptography, hashing, streaming-algorithm
---


# Question
Title: Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language
I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular language, I would appreciate if the answer could e given step by step, I really wnat to understand how it works .

Thank you :)

Show that $\\{xy : x \in \\{a\\}^\*, y \in \\{b\\}^\*, |x| = |y|\\}$ is a not a regular language

# Answer
Assume L is regular and is recognised by a state machine with N states. Then the strings $a^k$ for 0 ≤ k ≤ N cannot all end up in different states, because that would be N+1 different states. Therefore there are k ≠ k' such that $a^k$ and $a^{k'}$ end up in the same state.

If $a^k$ and $a^{k'}$ end up in the same state, then $a^k w$ and $a^{k'} w$ also end up in the same state, for every w. We pick $w = b^k$, and $a^k b^k$ and $a^{k'} b^k$ end up in the same state. However, the first is in the language and the second is not. Therefore the state would have to be both an accepting and a non accepting state, which is not possible. Therefore L is not regular.
> 1 votes

# Answer
Let $L$ be your language. Suppose towards a contradiction that $L$ is regular and let $p$ be it's pumping length. Consider the word $a^pb^p \in L$. By the pumping lemma we can write it as $a^i a^j b^p$ with $j \ge i$ in such a way that, for all $k \ge i$, $a^i a^{jk} b^p \in L$. Pick $k=0$ to obtain $a^i b^p \in L$. This provides the sought contradiction since $i \< p$.
> 0 votes

# Answer
isn't this the same problem: https://stackoverflow.com/questions/2309752/why-is-anbn-n-0-not-regular

$if \\,\\,\\,\\, |x|=|y| \\,\\,\\,\\, then \\,\\,\\,\ L = \\{a^n b^n \mid n \geq 0\\} $
> 0 votes

---
Tags: formal-languages, regular-languages, pumping-lemma, nondeterminism
---


# Question
Title: Max flow algorithm for floating-point weights and E~=10*V
Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e. `O(V^3)` algorithms take too much time, but `O(E^2)` algorithms are much more preferable. More specifically, you can assume `V~=1M` and `E~=10M` where `M` stands for millions.

# Answer
> 2 votes
Push-relabel with 'highest label first' heuristic is considered state of the art for a long time. It has a theoretical running time of $O(n^2 \sqrt{m})$, but runs very fast in practice. As far as I know, most algorithms that uses sophisticated data structures such as dynamic trees are outperformed in practice. You can look at the paper "Computational investigations of maximum flow algorithms" which shows some measurements of different running times of algorithms. The push-relabel algorithm is available in boost in C++, JGraphT or JGAlgo in Java, and many more libraries (not in networkx).

Regarding floating points, almost all algorithms should work for them theoretically (unless scaling is used, which is not common for max flow). In practice, there are errors because of rounding, but in most libraries you can specific an epsilon of precision which should solve the problem. Boost support template for the capacity type, so you can use other types other than double for it, such as big decimal, but it would probability be ~1000 times slower.

# Answer
> 1 votes
Orlin's algorithm can solve max flow in sparse graphs in $O(|V| |E|)$ time. See

Max flows in O(nm) time, or better. James B. Orlin. STOC 2013.

You'll have to decide whether the potential speedup is worth the time to implement it, as I believe the algorithm is quite complex. I don't know whether the algorithm is better in practice.

Perhaps someone else will have better suggestions for you.

---
Tags: graphs, network-flow, floating-point, sparse-matrices
---


# Question
Title: Are any "standard" complexity classes uncountably infinite?
(This is a somewhat fuzzy question.)

I believe that most of the "standard" complexity classes that one comes across in complexity theory are countably infinite, because they are defined in terms of decision problems that can be solved by Turing machines with certain prescribed capabilities, and the set of Turing machines (on a given alphabet, etc.) is countable.

But certain complexity classes, like ALL, are uncountably infinite. Are any other "practically important" classes that come up on complexity theory uncountably infinite? What about in computability theory?

# Answer
> 7 votes
Nonuniform complexity class P/poly is uncountable. We can just choose for each input length its own circuit, so for any subset $S \subset \mathbb{N}$ the language $L\_S = \\{w \colon |w| \in S \\}$ is in P/poly.

In general, nonuniform/advice complexity classes are usually uncountable for the same reason.

---
Tags: complexity-theory, computability, complexity-classes, uncountability, infinity
---


# Question
Title: Why is the block size chosen to be q-1 for Reed-Solomon codes?
Consider a Reed-Solomon code over a finite field of $\mathbb{F}\_q$. Why is the typical block size chosen to be $q-1$ `[1][2][3]`? The reasoning I saw around this is that in order to maximize the rate for a fixed minimum distance. But wouldn't choosing $q$ as the code size would be even slightly better? Does it have to do something with how BCH decoders work? Wikipedia lists both $q$ and $q-1$ as a possible good choice for the block size, but doesn't cite any reference.

```
[1]: Manz: Fehlerkorrigierende Codes
[2]: Pretzel: Error-correcting Codes and Finite Fields
[3]: Hoffman: Coding Theory: The Essentials

```

# Answer
Reed Solomon codes are cyclic. A cyclic code \[over whatever Galois field\] of length $n$ is defined with respect to reduction modulo $x^n-1$ to get the cyclic property.

Now, the generator polynomial $g$ and the parity check polynomials $h$ are defined by $g(x)h(x)=x^n-1,$ more exactly one is chosen and then the other one is determined using this equation.

The factorization of $x^n-1$ is crucial in determining the properties of the code. The nonzero elements of a finite field $GF(q)$ obey the equation $x^{q-1}-1=0,$ and form the multiplicative group $GF(q)^{\ast}.$

Thus the only choice is to make the length of the code either $q-1$ or a divisor of $q-1.$ This is because, it is known that $x^n-1$ is divisible by $x^m-1$ if and only if $n$ is divisible by $m.$ Usually we take $n=q-1,$ for efficiency since it gives the longest code for a fixed alphabet size.

**Remark:** For Reed-Solomon which have alphabet $GF(q)$ the factorization is trivial (no cyclotomic cosets need to be computed which are used to determine minimum distance for binary codes). So we take $g$ to have a sequence of consecutive powers of $\alpha$ the primitive element as its roots.
> 0 votes

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


# Question
Title: If A U B and A ∩ B are recognizable, then is one of A, A', B, B' also recognizable?
I know that if decidability of $A \cap B$ and $A \cup B$ doesn’t guarantee the decidability of any of $A$ or $B$. We can prove that:

ATM is not decidable. Since decidable languages are closed under complementation, ATM' is also not decidable. But $\textrm{ATM} \cup \textrm{ATM}' = \Sigma^\*$ and $\textrm{ATM} \cap \textrm{ATM}' = \varnothing$ both are decidable.

But what about recognizability?

# Answer
> 1 votes
Then answer is no.

The language $A$ of Turing machines that halt on every input is not recognizable, but its complement $A^c$ is also not recognizable. Then both $A \cup A^c = \Sigma^\*$ and $A \cap A^c = \varnothing$ are recognizable, but neither are $A$ nor $A^c$.

---
Tags: turing-machines, undecidability, sets, turing-recognizable
---


title: Turing Machine Decidability

text:
# Question
Title: Turing Machine Decidability
Consider the language $L = \\{\langle M\_1,\ M\_2 \rangle \mid \exists x : x \in L(M\_1) \cap L(M\_2)\\}$. Show that $L$ is not decidable.

I'm attempting a proof by contradiction but I'm having trouble with the Turing machine part.

# Answer
> 1 votes
Suppose you chose $M\_1 = \Sigma^\*$. Could you find a $M\_2$ that would fill the bill here?

---
Tags: complexity-theory, turing-machines, theory
---


# Question
Title: Intermediate Representation vs Byte Code
The Wikipedia page about interpreters mentions the following three strategies

> 1. Parse the source code and perform its behavior directly
> 2. Translate source code into some efficient intermediate representation or object code and immediately execute that
> 3. Explicitly execute stored precompiled bytecode made by a compiler and matched with the interpreter Virtual Machine.

Isn't byte-code intermediate representation? What is the difference between 2 and 3? The use of VM?

# Answer
> 3 votes
This is from just the summary of the article, and I'm not sure that it is a terribly helpful one.

What I think the author was trying to say is that the difference between 2 and 3 is *who* translates the source code into an intermediate representation. If that translation is done *ahead* of time (as you see in JVM languages or dotnet), that's more or less number 3. If it's done by the interpreter (i.e. the input to the interpreter is source code), then that's more like number 2.

Note that there is also a fuzzy boundary between 1 and 2. Tree-based IRs do exist, so at what point does a very sophisticated abstract parse tree become an efficient intermediate representation?

---
Tags: interpreters
---


# Question
Title: Efficient algorithm for finding a vector to maximize the number of positive dot products with a given set (finding the maximum overlap of half-spaces)
I have a large set $\mathbf{V}$ of vectors in $\mathbb{R}^d\setminus\\{\mathbf{0}\\}$ and need to find a vector $\mathbf{u}$ that maximizes $\sum\_{\mathbf{v}\in\mathbf{V}}\mathbf{1}\_{\mathbf{u}\cdot\mathbf{v}\>0}$, which is to say the count of vectors in $\mathbf{V}$ that have a positive dot product with $\mathbf{u}$. Alternatively, one could also phrase this problem as finding a maximum subset of the half-spaces defined by the elements of $\mathbf{V}$ such that the intersection of those half-spaces is nonempty. I am wondering if an efficient algorithm for this problem is known.

Just to rule out an obvious idea, normalizing the vectors in $\mathbf{V}$ and taking their average does not solve the problem. In particular, even in two dimensions a normalized set like $\mathbf{V}=\left\\{\left(1, 0\vphantom{\frac{0}{0}}\right)\\!, \left(-\frac{5}{13}, \frac{12}{13}\right)\\!, \left(-\frac{5}{13}, -\frac{12}{13}\right)\right\\}$ would have average $\left(\frac{1}{13},0\right)$, which only has a positive dot product with $\left(1, 0\vphantom{\frac{0}{0}}\right)$, whereas an alternative like $\left(-1, 0\vphantom{\frac{0}{0}}\right)$ has a positive dot product with both $\left(-\frac{5}{13}, \frac{12}{13}\right)$ and $\left(-\frac{5}{13}, -\frac{12}{13}\right)$.

A correct but slow algorithm would be to consider all size-$(d-1)$ subsets of $\mathbf{V}$, use each subset to construct a candidate vector orthogonal to everything in the subset, and then keep whichever of these candidates maximizes the count. But the run time of that design has $d$ in an exponent, so it scales poorly. Is there something better?

Context that I don't think affects the answer, but I will include anyway in case I am wrong, and it is relevant:

* In this particular case, I actually have $\mathbf{V}\in\mathbb{Z}^d\setminus\\{\mathbf{0}\\}$, so the components are in fact integers.
* For the particular application, I would be very surprised if the answer $\mathbf{u}$ did not have all positive components, though I still expect vectors in $\mathbf{V}$ to have components with mixed signs.
* I also suspect that the subspace of solutions will be connected, and it would be nice to compute a $\mathbf{u}$ that is in the middle of this space so that its quality isn't super sensitive to issues with precision, rounding, etc. later on.

# Answer
> 1 votes
If I understand your question correctly, you are describing a problem that is almost identical to the optimization problem in Support Vector Machines. The only difference is that in your case the separating plane is not offset from the origin, i.e. $b=0$. If a $u$ exists that makes all dot products positive, you could solve the following convex optimization problem:

$$ \begin{matrix} \mathcal{minimize}\_u && 0 \\ \mathcal{subject} \\; to && V^Tu \ge 1 \end{matrix} $$

If violations are possible, you could introduce a slack/error vector $e$ solve the following problem:

$$ \begin{matrix} \mathcal{minimize}\_{u,e} && \max\_i{e\_i} \\ \mathcal{subject} \\; to && V^Tu \ge 1-e \\\&& e \ge 0 \end{matrix} $$

Which, again, is a convex optimization problem. There many open-source convex solvers available, like CVXOPT and CVXPY for Python.

---
Tags: algorithms, optimization, linear-algebra, mathematical-programming
---


# Question
Title: Upper bound on output of halting transducer
My question is simply this: is it possible to upper bound the output length of a **halting** turing machine? I.e., is there a function $f$ such that for every halting machine $M$ and every input $x$ we have $|M(x)| \in O(f(|x|))$?

On the one hand, it seems like yes because every halting machine will leave some finite string on the tape so surely each machine has a longest output given all inputs of length $n$. But on the other hand, it feels like no because whatever bound $O(f(n))$ you give me, I could build a machine that writes $f(n)$ on the tape $f(f(n))$ many times or something. So I'm a bit confused...

For comparison, clearly a P time/space machine can only output strings of length $poly(n)$. Is this cutoff simply the time/space complexity? So what's the smallest class with unbounded output length?

# Answer
The answer is yes! Fix your favorite flavour of Turing machines (for instance: non-deterministic Turing machines with a single tape), and fix both the input and output alphabets. Then for each $s \in \mathbb{N}$, there are finitely many machines with $s$ states (up to relabeling the states). Also, for each $n \in \mathbb{N}$, there are finitely many inputs of size $n\in\mathbb{N}$, so the function $$ f\colon (s, n) \mapsto \max\\{|\mathcal{M}(x)| \mid x \text{ is an input of size $n$ and $\mathcal{M}$ is a halting machine with $s$ states}\\} $$ is well-defined. Then, let $g \colon n \mapsto f(n,n)$.

**Claim:** If $\mathcal{M}$ is a halting Turing machine, then $|\mathcal{M}(x)| \in \mathcal{O}(g(|x|))$.

*Proof:* Let $s$ be its number of states. Then for each input $x$, we have $|\mathcal{M}(x)| \leq f(s, |x|)$. Whenever $|x| \geq s$, we have $f(s,|x|) \leq f(|x|, |x|) = g(|x|)$ , and hence for every halting machine, there is an $n\_0$ (namely its number of states) such that for every input $x$ of size $n \geq n\_0$, $|\mathcal{M}(x)| \leq g(n)$.

Interestingly, the exact same proof works if you replace "size of the input" by "number of steps", and so there is a function $g'$ such that for any halting Turing machine $\mathcal{M}$, the function $$n \mapsto \text{maximal nb of steps executed by $\mathcal{M}$ on a input of size $n$}$$ is a $\mathcal{O}(g')$.
> 3 votes

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


# Question
Title: Find multiple order-statistics of an array
Given array $a$ of size $n$ and array $p$ of size $m$. How we can for every $i \< m$ find $p\_i$-th order statistics of array $a$ in $O(m log(n) + n)$?

We can find order statistics separately, but it will be $O(mn)$. How can we do better?

# Answer
We would need to choose a tree data structure that preprocesses $n$ elements in $O(n)$ and processes each of the $m$ order-statistics queries in $O(log\ n)$, leading to a complexity of $O(m\ log\ n + n)$. Notice when $m \> n$, this will be less optimal than a static $O(n\ log\ n)$ solution.
> 1 votes

---
Tags: algorithms, time-complexity, search-algorithms
---


# Question
Title: Show that exist a finite set of clauses F in first-order logic that Res*(F) is infinite
I'm kind of desperate at this point about this question.

A predicate-logic resolution derivation of a clause $C$ from a set of clauses $F$ is a sequence of clauses $C\_1,\dots,C\_m$, with $C\_m = C$ such that each $C\_i$ is either a clause of $F$ (possibly with the variables renamed) or follows by a resolution step from two preceding clauses $C\_j ,C\_k$, with $j, k \< i$. We write $\operatorname{Res}^\*(F)$ for the set of clauses $C$ such that there is a derivation of $C$ from $F$.

The question is to give an example of a finite set of clauses $F$ in first-order logic such that $\operatorname{Res}^\*(F)$ is infinite.

Any help would be appreciated!

# Answer
This is Exercise 83 in Schöning's book "Logic for Computer Scientists". Similarly, the solution to this problem can be found in the original paper of Robinson. He gives an example with clauses $Q(a)$ and $\neg Q(x) \vee Q(f(x))$.
> 1 votes

---
Tags: logic, first-order-logic, predicate-logic
---


# Question
Title: Dynamic Programming problem about intervals
This is algorithms and data structures assignment and I have been thinking 3 days about it. You are given N sections, placed on numeric axis. Numeric axis is divided by unit intervals. Each section in described by two integers - coordinates of left and right endpoints and it covers corresponding number of intervals. From existing sections, you must remove K sections so that remaining sections in total should cover maximum number of unit intervals. You are given N, K and N different sections. (N\<=100000, K\<=100). Program should return one integer - maximum possible number of intervals covered by remaining sections after removing K of them. My initial thought was that I needed greedy algorithm because it really looked like scheduling greedy algorithm. But now I understand that it is dynamic programming problem. My most accurate solution is:

1. removing all sections that are covered by another section, since it does not contribute to any maximization or covering intervals.
2. If number of removed sections \>= K, then result is currently covered intervals.
3. Otherwise, I implemented dynamic programming using top-down approach with memoization. Solution to current sections (for example, count = M) and K, is maximum among all M-1 sized subsets and K-1; Removing redundant intervals is fast, but recursion increases rapidly and is slow. I could not come up with bottom-up approach. For tabulation method I think it should have K as columns and N as rows and base cases are pretty trivial, but I do not get how to fill grid cells. Any help, hints or advice would be appriciated.

# Answer
It’s difficult. I wouldn’t be surprised at all if it is NP-complete. Many NP-complete problems you can start with things that must be optimal. Like remove all sections covered by another section. Then take all sections that must be optimal: If yo find the k smallest intervals, then take all intervals that are the only coverage for x units where x \>= k-smallest interval. Then remove units from the sections that are already covered. For example if you had 101-120 and 115-121 and the k-smallest interval had length 5, 101-120 goes into the solution, and 115-121 is changed to 120-121.

And if this finds no solution then you might pick the largest interval (changing other intervals) until k intervals remain.
> 0 votes

---
Tags: algorithms, dynamic-programming, intervals
---


# Question
Title: Why aren't all smaller components of 64-bit registers accessible and readily usable?
A register in a CPU can be much more well utilized if it could be divided and its parts can be used independently. For example, if you need 8 8-bit values, you could just use a single 64-bit register, and each 8-bit segment could be treated independently of one another. But the way CPUs are designed, using 8 64-bit registers with only the first 8 bits of each used is the norm. And extracting the higher order bytes typically requires a shift and a bitmask. Why are they designed like that?

# Answer
> 3 votes
I think there are two main reasons explaining the current design:

1. it is a historical choice that took into account the manufacturing process (hardware complexity and realization cost) which had to be reduced,
2. the architecture currently used allows you to do what you are asking for at a reasonable price, paid in terms of additional clock cycles (through shifts and bit-masking).

It is in theory possible to design a CPU having some flag that switches the register's operation mode from the classic one to the one you suggested, however, this choice would require additional circuitry for managing concurrency-related issues, namely, locking, caching, and synchronization of the CPU pipeline.

Let's suppose the converse, that is, the CPU was always in this mode. In that case, you were just asking for many more tiny 8-bit long registers. In this situation, I wonder: how could I employ 64 (or 32) bits to represent big numbers? I think I would be forced to implement all relevant integer operations (with carries, borrows, and the rest). Nowadays, we want those operations to be out of the box.

Lastly, observe that there exist microprocessors behaving vaguely the way you describe: Intel CPUs historically split registers in sub-registers that can be manipulated directly but with some limitations.

# Answer
> 2 votes
The problem is *rename registers*.

An out-of-order processor that is told “add register r2 to r1” will not actually modify r1 but find a new register rx, set rx = r1+r2, and from then on uses rx instead of r1. This is done because there might be other unfinished instructions that still need to use the original value of r1.

Now if you say “add r2 and r3 and store in the lower 8 bits of r1” that instruction would need three operands -r1,r2 and r3- to store the result into rx.

Intel processors have these instructions and they are slower than larger instructions and avoided.

---
Tags: cpu
---


# Question
Title: At what case/problem, Binary Insertion Sort would be faster than Insertion Sort?
We know Insertion Sort would be faster than Merge Sort and Quick Sort for nearly sorted data. What about Binary Insertion Sort? At what case is it better than Insertion Sort?

Also, is there a better solution than Binary Insertion Sort, for the problem is solves better than Insertion Sort?

# Answer
> 1 votes
First, notice that binary insertion sort and insertion sort both do the same number of permutations between elements.

The main difference between the two is the number of comparisons. If comparisons are hard/time-consuming relatively to permutations, the binary insertion sort becomes interesting.

As an example, in my school, there is a limited number of students we can welcome, and we have to make some kind of ranking. We use binary insertion sort because the most time-consuming task (done by humans) is the comparisons of candidates.

With binary insertion sort, for an array of length $n$, the number of comparisons done is roughly: $$\sum\limits\_{i=2}^n\log\_2(i) = \log\_2(n!)$$ This is better than the $n\log\_2 n$ comparisons done by merge-sort or the average $1.4n\log\_2n$ comparisons done by quick-sort (see here), or $2n\log\_2n$ comparisons done by heap-sort. I am not sure there are better algorithms in number of comparisons.

# Answer
> 0 votes
Insertion sort is faster than quicksort if o(log n) (that is little o, not Big O) items are in the wrong place. It will move o(n log n) items. This is slower than better methods which run in O(n) if the number of items in the wrong place is O(n / log n).

Binary insertion would use log n steps to find where to insert element k for a total of n log n. So when insertion sort is faster than quicksort, binary insertion isn’t.

---
Tags: sorting
---


# Question
Title: David Deutsch says "number of atoms in universe is finite", but then says "number of programs of all finite lengths is infinite". Contradiction?
From the book "Fabric of reality" by David Deutsch.

> We know from quantum theory that all such variables are quantized, and therefore that, no matter how the computer works, the set of possible programs is discrete. Each program can therefore be expressed as a finite sequence of symbols in a discrete code or computer language. There are infinitely many such programs, but each one can contain only a finite number of symbols. That is because symbols are physical objects, made of matter in recognizable configurations, and one could not manufacture an infinite number of them

So, why the list of programs is infinite if the length of each program is finite?

Namely “one can contain only a finite number of symbols” contradicts “There are infinitely many such programs”

---

I look at https://cs.stackexchange.com/a/58057/109204

> The number of programs of all finite lengths is infinite. This is depressingly easy to prove. In C++, take the programs which (apart from decoration) say x=1, x=2, x=3,… (and so on for ever) and you have your infinite list of programs.

But if “one could not manufacture an infinite number of \[configurations of matter\]” then `x` cannot be infinitely big

> P.S. also, it means that energy in universe is finite, and one day we will spend all energy of universe and die, since humans are robots

Cross posted https://physics.stackexchange.com/questions/791746/david-deutsch-says-number-of-atoms-in-universe-is-finite-but-then-says-numbe

# Answer
I understood now (after "program has a finite size") - this is "potential/unrealized vs actual/realized infinity" problem.

I, like Zeno in Zeno paradox with Achilles vs turtle, was thinking that something is an actual/realized infinity, while in reality it is potential/unrealized infinity.

Let me explain.

GIVEN only finite amount of matter is available to store programs AND list of programs is ACTUALLY (because it's a set like `{1,2,3,...}`) (countably) infinitely big AND each program is stored as FINITE string `xxx` where `x` is 0 or 1 =\>

I was thinking in the end of list I will run out of space for `xxx`, but I will not, `xxx` is only POTENTIALLY (because it's a process like `1,2,3,...`) (countably) infinite, `xxx` will never be ACTUALLY REALIZEDLY INFINITE, it will always be FINITE !! (it doesn't matter if our universe has finite or infinite amount of atoms or I need to build program from atoms in finite amount of time from finite amount of matter, I will not run out of building blocks)

Note: I say that `xxx` is both finite and potentially infinite. Is this a problem? TODO

UPDATE1: and then David Deutsch writes that each program creates virtual reality environment that can run finite or infinite time. Cangoto environments + cantgoto environments = all environments. Probably similar to: rational numbers (computable, set is countable , can be printed so that text have finite length) + irrational numbers (uncomputable, set is uncountable , infinite when printed, e.g. pi is a result of infinite computation like `1/(1+(2/(1+3/...)))`) = real numbers
> 1 votes

# Answer
A good analogy would be the integers: There is an infinite amount of finite integers. We can prove that by contradiction: Let's say there was a largest finite integer $i$, then $(i+1)$ would be even larger and still finite. So there is no finite limit. A very similar argument can be made for computer programs by appending another statement instead of adding $1$.

Clearly, programs larger than the number of the atoms in the universe are impractical. And there are even much smaller programs that will run longer than the universe will exist (without running eternally). But that is kind of the point of David Deutsch's statement.
> 20 votes

# Answer
The key distinction here is that a program is a concept. A concept is distinct from the place that concept is represented or stored.

You can have the same program represented by different physical chunks of matter. The program `print("Hello World")` is the same program whether it is stored on my computer or on yours.

You can have the same program represented by arrangements of matter in different ways: it is the same program whether it's magnetic wobbles on a floppy disk of physical wobbles on CD, or even blobs of ink on a page.

Meanwhile if I take the exact location on my hard drive where the binary code is stored and overwrite the file, I have destroyed that physical representation of the program but I have not erased the concept itself.

Now, if you'll allow that the program as a concept can survive the destruction of its physical representation, then you might start to imagine the program as a concept even if it has not been represented at all. For example, I might meaningfully talk about the program that I'm trying to write, as a concept, but it hasn't been written yet. Even the neurons in my brain have just the vague outline of what the finished program ought to be. Even so, I can talk about it, saying how it should behave and even how it's different from another similar buggy program which I'm trying not to write!

Now, if the program as a concept does not need to have been written down in order to exist, it may then make sense that it does not need to be possible to write it down. So for example, I can meaningfully talk about "A program which does a physics simulation of a universe like ours except with a googol particles in it." Since we don't have a googol particles in our universe, there is no way that we could ever actually build a computer able to store and run that program. But we can talk about it, as a meaningful concept. We can even imagine that if we only had a bigger universe, then we could build a big enough computer!

From there, it's only the slightest jump to consider that there's infinitely many such programs which are finite in length (they could be written down given a big enough universe) even though our actual universe is too small.
> 7 votes

# Answer
Because the number of possible lengths is infinite.

---

Consider the set of all possible sequences of the 26 upper case letters of the English alphabet, for all possible lengths of such a sequence.

The possible symbols in each sequence in such a set are themselves a finite set. There are only 26.

The possible lengths, though, are infinite, because the length can be any positive integer, and there is no ‘largest integer’ (you can always add 1 to an integer to get a larger integer).

Because the possible lengths are infinite, the set as a whole is also infinite. The same is true independent of how many possible symbols there are, as long as there is at least one possible symbol.
> 4 votes

# Answer
Your reasoning is well-founded, but begins from different axioms than the ones Deutsch is using. The concern you're raising boils down to "how can *any* infinite set exist given there is only a finite amount of matter in the (observable) universe?" This is the line of inquiry that leads to mathematical finitism. L.E.J. Brouwer, for instance, would probably have said that it is impossible to write down the list of all Turing machines in a finite amount of *time*, even if supplied with infinite material to write on, therefore the idea of such a list is nonsensical.
> 0 votes

# Answer
It just means that it is not possible to write down all programs of finite lengths. You’ll probably run out of atoms at programs of length 200 or 300.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Expected number of mistakes grows logarithmically in number of iterations - improving performance?
I am reading a paper (link) in which an algorithm proposes a solution $\hat{\mathbf x}^{(t)}$ in each iteration $t = 1, \dots, T$, and each time, learns the true solution $\mathbf x^{(t)}$, so we learn whether the algorithm made a mistake, i.e. $\hat{\mathbf x}^{(t)} \neq \mathbf x^{(t)}$.

In Theorem 9, we learn that the expected number of mistakes made by the algorithm after $T$ iterations is bounded by something like $O\left(\log(T)\right)$, ignoring terms I don't want to focus on here.

**Question:** Can we interpret this as implying that the algorithm is getting better over time? Asymptotically, $T$ will dominate $c \log(T)$ for some $c \> 0$, so does this imply that over very many iterations, the algorithm should eventually rarely make mistakes?

# Answer
> 1 votes
Yes, it becomes clear if you see the error ratio:

$$r\_T := \frac{T}{\log T} \ .$$

$r\_T$ is a monotonic (strictly) decreasing sequence and $\lim\limits\_{T\to 0} r\_T = 0$, but $r\_T\>0 \ \forall \ T \> 1$. This means that the error ratio becomes smaller and smaller as the number of iterations grow, until it becomes negligible.

However, be careful when working with asymptotics. $O(\log T)$ is just an asymptotical behavior, it can be that in practice, for a reasonable number of iterations, we don't have this improving behavior.

---
Tags: algorithms, algorithm-analysis, asymptotics, big-o-notation
---


# Question
Title: is this a contradiction? "stating there are an infinite number of programs but that a program cannot be infinitely long is a contradiction"
i saw this comment here : David Deutsch says "number of atoms in universe is finite", but then says "number of programs of all finite lengths is infinite". Contradiction?

> ""stating there are an infinite number of programs but that a program cannot be infinitely long is a contradiction" That's not a contradiction. There are an infinite number of finite binary strings, but a finite binary string cannot be infinitely long (by definition)."

I would have thought that this is indeed a contradiction, if we take natural numbers for example, we know that there are an infinite number of arrangements numbers can make, we also know that numbers can be infinitely long because we can always do +1. so if there are an infinite number of programs possible in this scenario, we would have to assume an infinite number of additional bits to add to the end of the program, otherwise we would come to a finite number of arrangements with the number of bits present we have to play with, allowing an additional unique "program" at this point would require an additional bit to be added to the mix just like the proof by contradiction to prove that infinite numbers exist, why can't we use proof by contradiction to prove that there are infinite programs and that programs can be infinitely long?

# Answer
> 2 votes
This is not a contradiction: the two numbers are unrelated.

Atoms are objects that we can observe and count in the physical world, The number of atoms in the universe is a physical property of the natural world, as described by physics.

Programs, as described in this textbook, are not physical entities; they are mathematical constructs within a mathematical model of programming. Of course we can implement programs in the real world, but the text is not about such real-world implementations, it is about a mathematical abstraction.

Therefore, the two numbers are unrelated.

The number of all programs of finite lengths is indeed infinite. Do not confuse the number of elements in a set with properties of the individual elements of that set. To see this, let's look at natural numbers. There are infinitely many natural numbers. We can construct all kinds of things based on these numbers. For example, we can construct intervals, such as

1. 1 to 3 inclusive
2. 2 to 10 inclusive
3. 5 to infinity

The intervals that go to infinity are infinite in the sense that they contain infinitely many numbers; but they have a finite description, as you can see.

Now consider the set of only the finite intervals, such as the first two examples. Each of these intervals is clearly finite; but there are infinitely many of them, so the set of finite intervals is infinite.

Programs as discussed in the text you refer to are more complicated mathematical constructs than intervals, but the same principle applies to them: if we limit ourselves to the set of finite programs (which we usually do), each of these programs is finite, but there are infinitely many different ones, so the set of them is infinite.

---
Tags: turing-machines
---