title: Q-learning in a Dynamic environment

text:
# Question
Title: Q-learning in a Dynamic environment
I am new to reinforcement learning. Lately, I have learned Q-learning using the following tutorial.

Is Q-learning still possible if the environment is dynamic. Using the environment of the tutorial as an example, in some states it is possible to go from room 0 to room 1 and and it is not possible to go from room 0 to 4.

Is it possible to use Q-learning in a problem like that? if not is there an algorithm that handle dynamic environments?

# Answer
> 5 votes
In general you can't change the state and action spaces (rows and columns of your reward matrix) since that changes the underlying model that you are sampling with Q-learning. It'd be similar to changing the population you're sampling when statistically sampling. Hence, you have to define a set of actions and states that don't change in order to use Q-learning. Instead of the house graph, you'd need something else. Ideally you'd have to come up with a set of states and actions that didn't change as the house's topology changed. E.g. actions could be strategy to use could be the action given the number of rooms in the house and total number of edges (note: this'd probably be a poor choice, but I needed an example.).

All that said Q-learning albeit a little slow is pretty robust to some types of disturbances. If the model doesn't change significantly (e.g. you add a room) and you are exploring a large state space (statistically), then your older policies (solved Q matrices) might be nice breadcrumb trails for your new algorithm's exploration strategy, and the algorithm may re-learn much faster. However, I don't know about the theoretical guarantees (look into terms like "cross learning").

# Answer
> -1 votes
You should check this paper: https://ieeexplore.ieee.org/document/7849368 It discusses Q-Learning in a dynamic environment.

---
Tags: machine-learning, artificial-intelligence, reinforcement-learning
---


# Question
Title: Did Wheeler really believe that physics was undecidable?
John Archibald Wheeler was a famous physicist.

It has been stated that he thought that there was a strong connection between undecidability and quantum physics:

> This idea was given an early formulation by Wheeler himself: in unpublished notes to a discussion held with, among others, Roger Penrose and Simon Kochen, he identifies the point of origin of the ‘quantum principle’ as the undecidable propositions of mathematical logic

(See Jochen Szangolies, Epistemic Horizons and the Foundations of Quantum Mechanics.)

But then, this same physicist proposed that the universe was similar to a computer and that reality emerged as digital informational processes in form of bits (It from Bit): digital physics.

As far as I know, digital physics models cannot be undecidable. They must be decidable (If not, we could never construct an algorithm which would get a correct answer to a yes/no question)

So, what is happening here? Did Wheeler change of mind?

# Answer
The inference "the universe would be completely computable, so no undecidable/uncomputable things could exist" is invalid.

In the effective topos, where everything is computable, there are many undecidable phenomena. For example, all real numbers are computable, but equality of real numbers is undecidable (and computable).

To give you an idea how this happens: equality of reals is a map $\mathbb{R} \times \mathbb{R} \to \Sigma$ which is implemented by a Turing machine that takes (Turing machines that compute) reals $x$ and $y$ and returns a non-boolean truth value represented by a Turing machine which terminates if, and only if, $x \neq y$.

In contrast, equality of natural numbers is decidable. It is a map $\mathbb{N} \times \mathbb{N} \to \\{0,1\\}$ which takes two natural numbers and outputs either $0$ or $1$, depending on whether they are equal.

As far as physcists are concerned, I would be careful about learning computability theory from them. I wouldn't want anyone to learn physics from me.
> 6 votes

---
Tags: logic, undecidability, physics, incompleteness
---


# Question
Title: How to find the nearest point in the coordinate system
There are so many points in the coordinate system. When a specific point is given in the coordinate system, I want to find the closest point to the straight line distance. For example, if you have 800 points, calculate the distance 800 times and find the smallest value. But I want to make more efficient algorithm that doesn't execute 800 times due to that it might be sorted in a certain order before searching. That is, if the points is put in a certain order, Could you recommend some notions?

# Answer
So, if I understand correctly, you have a set $S$ of points in some space (do you have a specific dimension ?), and a point $x$, and you want to find the point of $S$ that is the closest to $x$ ?

If this is indeed what you are trying to do, have a look at K-d trees and Voronoï tesselation. These methods are based on space partitioning to make queries faster.
> 1 votes

# Answer
In addition to GBat's answer, you can also take a look at binary space partitioning (BSP), like $k$-d tree it needs precomputation beforehand, but once the structure is created, each search can be done in $O(\log n)$.
> 1 votes

---
Tags: algorithms, computational-geometry, nearest-neighbour
---


title: Introduction to computer science for ML

text:
# Question
Title: Introduction to computer science for ML
I have learned python syntax (from books like *fluent python* or *python cookbook* etc.) and I want to learn the **underlying concepts of computer science** (in an abtract way), do you have some books/courses to suggest to me (others than algorithms and data structures' resources)

I've found a book called *Python Programming. An introduction to computer science* by John Zelle, but I am worried about the potential huge overlap between the above-mentionned books and this one.

Some books found while brwosing the web, but I don't have an idea about its usefulness :

* Structure and Interpretation of Computer Programs by Harold Abelson, Gerald Jay Sussman, and Julie Sussman
* Compilers: Principles, Techniques, and Tools by Alfred V. Aho
* How to design computer programs by by Matthew Flatt, Matthias Felleisen, Robert Bruce Findler, and Shriram Krishnamurthi
* Theory of Computation by Michael Sipser

PS: My backgraound is a Bachelor degree in Mathematics. My goal is to gain sufficient knowledge of CS concepts.

Thanks

# Answer
Computer science is a very broad field - see this Wikipedia outline. Machine learning is just one topic within the field, and there are other parts of computer science that have little or no overlap with machine learning. For example, the theory of compiler design is unlikely to be of much use to you when studying machine learning.

My suggestion is to approach this from the opposite direction. Start with a text that provides an introduction to machine learning. An introductory text should include an overview of other computer science topics that are pre-requisites. If you want to or need to dig into any these wider topics in more detail, then you have a more focussed goal than trying to understand the whole of computer science.
> 1 votes

---
Tags: machine-learning, software-engineering, books
---


# Question
Title: Why does coNP⊆NP∖P imply that the polynomial hierarchy collapses?
I was looking for some information on 1-in-3 SAT and came across this paper, last updated 9 days ago, which claims that the Polynomial Time Hierarchy collapses "to the level above P=NP". That's quite exciting if you ask me, although I don't have the toolkit to understand the actual proof. My question is about something much simpler.

Specifically, in the abstract on arxiv, the author writes,

> Our proof shows the structure formerly known as the Polynomial Hierarchy collapses to the level above P=NP. That is, we show that coNP⊆NP∖P.

Could anyone help me understand why these two statements are equivalent?

# Answer
> 5 votes
I believe the claim is more commonly written as $coNP \subseteq NP/poly$, but that of course does not immediately answer your question.

The fact that this implies that the polynomial hierarchy collapses is shown in Theorem 2 here:

Chee-Keng Yap. Some consequences of non-uniform conditions on uniform classes. *Theoretical Computer Science*, 26:287–300, 1983. doi:10.1016/ 0304-3975(83 ) 90020-8

If I understand correctly, $coNP \subseteq NP/poly$ is shown to be equivalent to $coNP/poly = NP/poly$ (unnamed corollary on page 292), and this would then imply $\Pi\_3 = \Sigma\_3$ (Theorem 2), implying collapse of the further hierarchy. For an actual proof, if you have access to the paper, I'll refer you there, I am not familiar enough with it to attempt an explanation now.

On an unrelated note, I believe the paper you are citing to be **incorrect** (but that would probably warrant a separate question?)

# Answer
> 4 votes
> \[...\] the structure formerly known as the Polynomial Hierarchy collapses to the level above $\text{P}=\text{NP}$.

This claim makes no sense. If $\text{P}=\text{NP}$, then the whole polynomial hierarchy is equal to $\text{P}$ and there is no level above that.

> That is, we show that $\text{co-NP}\subseteq\text{NP}\setminus{P}$.

$\text{co-NP}\subseteq\text{NP}\setminus{P}$ is unconditionally false, since $\text{P}\subseteq\text{co-NP}$ (and $\mathrm{P}\neq\emptyset)$.

I wouldn't recommend spending any time on this paper.

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


# Question
Title: Matrix Inversion in the complexity class $P$ seen as a decision problem
If the set $P$ is defined as the set of decision problems that can be solved by a deterministic Turing Machine in polynomial time, and matrix inversion using Gaussian elimination is $O (n^3)$, then how can I relate these two concepts to conclude that inverting a matrix is in $P$?

I suppose I need a way of converting a description of Gaussian elimination into a decision problem? Or maybe I am confused about the fundamentals

# Answer
> how can I relate these two concepts to conclude that inverting a matrix is in $\mathrm{P}$?

You can't. Your question contains two category errors.

* Complexity classes are classes of problems, not classes of algorithms. The complexity of a *problem* is the minimum amount of resources that are required to solve that problem, by any algorithm. "Resources" might be time, space, or other more exotic things. "Finding a matrix inverse by Gaussian elimination" isn't a problem: it's an algorithm (Gaussian elimination). The resource usage of any specific algorithm gives you an upper bound on the complexity of the problem that the algorithm solves, but it doesn't tell you anything else. When discussing a particular algorithm, if we're being careful about language, we talk about its running time and its space usage, rather than its complexity.
* $\mathrm{P}$ is a class of decision problems: problems with yes/no answers. Inverting a matrix isn't in $\mathrm{P}$ for the simple reason that it's not a decision problem. Gaussian elimination shows that matrices can be inverted in polynomial time, so it's in the class $\mathrm{FP}$ of function problems that can be solved in polynomial time. But, again, when being careful, we don't say that it's in $P$. On the other hand, related (but, admittedly rather artificial) problems such as "given a matrix $M$ and an integer $k$, is the $k$th bit of $M^{-1}$ a one?" are in $\mathrm{P}$ (if you're worried about corner-cases, define the answer to be "no" if either $M^{-1}$ doesn't exist, or it exists and has fewer than $k$ bits).
> 2 votes

# Answer
Gaussian elimination is an algorithm, you can’t frame it as a problem and thus it can’t be in $P$.

But matrix inversion itself is a problem and its decision version is as follows: “does matrix $M$ have an inverse?”

Gaussian elimination then is one possible way to prove that you can always answer that question in polynomial time, therefore matrix inversion is in $P$.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: In a Turing machine, what is the difference between the instruction table and the algorithm?
In a Turing machine, what is the difference between the instruction table and the algorithm?

The instruction table seems to be an algorithm for completing the task no?

# Answer
The Turing machine instruction table is a concrete implementation of the abstract algorithm. Usually, in one's everyday life as a computer scientist, there's not much to be gained by distinguishing these two concepts. Indeed, one can take the position that the Turing machine is the definition of "algorithm".
> 1 votes

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


title: Multiway Cut question

text:
# Question
Title: Multiway Cut question
I am trying to understand Multiway Cut, and basically how the Multiway Cut works. I am searching google many hours to find a good example to understand. A good example that I am trying to understand is this:

http://crab.rutgers.edu/~rajivg/studentTalks/multiwayCut.pdf

What I cannot understand, and here is the point I need your help, is how did he go from slide 12 to slide 13? How the graph on slide 13 was produced? How do I choose A1\*,A2\*,A3\* ??

# Answer
> 1 votes
The analysis of the approximation algorithm (join all min-cuts between a terminal and the contraction of the remaining terminals, excluding the heaviest cut) starts on slide 13. So there's nothing to compute, simply assume that $A^\*$ is the optimal solution with cuts $A\_i^\*$ separating terminal $i$ from the rest of the graph. To see the argument spelled out more explicitly read e.g. chapter 4 of Vazirani's "Approximation Algorithms".

---
Tags: algorithms
---


title: Do algorithms reduce?

text:
# Question
Title: Do algorithms reduce?
Given two problems A and B.

Given two algorithms a' and b'. a' solves A and b' solves B.

If A reduces to B and B reduces to A.

Then can we say anything about a' and b'? Are they the same?

# Answer
A reduction can be thought of a way to "rephrase" a problem in terms of another. This can be denoted using $A \to B$, $A$ reduces to $B$. This means that **if** you have an algorithm that solves $B$ **then** you also have an algorithm that solves $A$, since $A$ reduces to $B$, $A \to B$. Now you also have $B \to A$ so in some way, your problems are equivalent since they can be reduced to each other.

However, this does not imply much about the algorithms themselves because they can be arbitrarily bad. For example, the sorting problem has time complexity $O(n \log n)$. But an awful algorithm that sorts by testing all possible permutations has time complexity $O(n!)$.

The only thing we can say is that the algorithms aren't better (their time complexity isn't lower than) the problems themselves.
> 2 votes

# Answer
What do you *want* to say about $a'$ and $b'$? They can't possibly be the same algorithm unless $A=B$, since one of them solves $A$ and the other one doesn't. Even if $A=B$, they're not necessarily the same algorithm: if there's one algorithm that solves some problem, there are infinitely many (your favourite algorithm; count to two and then do your favourite algorithm; count to three and...).

It's so obvious that $a'$ and $b'$ are different except in trivial cases that having to ask the question suggests that you've misunderstood something, but I'm not sure what, so I can't be more helpful at the moment.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: What is the space complexity of Dijkstra Algorithm?
As per my understanding. The space complexity will be O(V). An array of V nodes will be created which in turn be used to create the Min heap.

But this link is stating that It is O(V^2)? I don't understand how it can be O(V^2)?

I have search the same topic in the Book entitled Introduction\_to\_Algorithms by Thomas H. Cormen but still not able to find the answer. I Don't understand what I am missing.

# Answer
Dijkstra's algorithm can be implemented in many different ways, leading to resource usage. The page you link gives the resource usage the implementations in the specific library being described.

I can't think of a way of implementing Dijkstra to use $|V|^2$ space, but I would note two things.

1. $O(\cdot)$ only gives an upper bound. Even if the implementation actually uses space $O(|V|)$, it's not *wrong* to say that it uses $O(|V|^2)$ or even $O(2^{|V|})$, just as it's not wrong to say that I earn less than a billion dollars a year. However, it would be unusual to say $O(|V|^2)$ if it was easy to prove the stronger bound of $O(|V|)$ (I also earn less than a million dollars a year), and it *is* easy to prove $O(|V|)$ for most implementations of Dijkstra.
2. The page quotes the running time as $O(s|E|\log|E|+V)$, where $s$ is the number of sources being considered. It's easy to imagine space usage of $O(s|V|)$ so maybe they wrote $O(|V|^2)$ since $s\leq|V|$. But that would also be strange, given that the quoted running time shows they're not afraid to use $s$.
> 3 votes

---
Tags: algorithms
---


# Question
Title: A deterministic FA for $0^*1^*$ is required
A **deterministic finite automaton without $\epsilon$ steps** for the language $0^\*1^\*$ is **required**. Any nice picture ? I have created a NFA for this language which has 2 states $Q\_1,Q\_2$, both are accepting, $Q\_1$ is initial, there is a move under $0$ from $Q\_1$ to $Q\_1$, a move under $1$ from $Q\_1$ to $Q\_2$ and finally a move from $Q\_2$ to $Q\_2$ under $1$.

# Answer
> 2 votes
To construct a DFA, note the following:

* An empty string or any string containing only $0$s is accepted, so any $0^\*$ is accepted.
* Zero or more $0$s followed by one or more $1$s is accepted, so any $0^\*11^\*$ is accepted.
* Zero or more $0$s followed by one or more $1$s followed by $0$ is rejected, so any $0^\*11^\*0$ is rejected.
* Any extension to a rejected string is also rejected (i.e. there is no route back from a rejecting state to an accepting state), so any $0^\*11^\*0(0+1)^\*$ is rejected.

This suggests a three state DFA with two accepting states and one rejecting state ...

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


# Question
Title: Partitioning a set so both parts have sum at least $c$ times the total sum
> Let $c\in(0,1/2\]$ be a constant. Given a set of positive integers with sum $S$, is there a partition into two subsets such that both subsets have sum at least $cS$?

If $c=1/2$, this is the famous partition problem which is NP-complete. What is known about the complexity for other values of $c$?

I posted the question to CS Theory several weeks ago. The only response was a comment that claimed that the problem is NP-hard, but the commenter never responded to my request for a proof or reference.

# Answer
> 3 votes
The problem is polynomial (even linear time) for any fixed $c \< 1/2$.

Assume no there is no item of size $\> (1-c)S$, otherwise it is a trivial no-instance.

If there is any item $w\_i$ with size $\geq cS$ we are immediately done because we can take one half of the partition to be that item.

Otherwise, all items are $\< cS$. Greedily taking items means we will exceed the target sum by less than $c S$, meaning the remaining items have weight at least $(1-2c)S$. If $c\leq 1/3$, the instance trivially is a yes-instance.

For $c\>1/3$, note that for the items smaller than $(1-2c)S$, we can use a greedy algorithm to assign them after we have a correct(\*) solution for the large items. The number of large items is at most $1/(1-2c)$, which, for fixed $c\<1/2$, is a constant. Thus, we can guess (in constant time) a solution for the large items, then use a greedy algorithm to distribute the small items. Note that the constant tends to infinity as $c$ tends to $1/2$.

(\*) Where correct means neither half of the partition exceeds $cS$ by more than $(1-2c)S$.

---
Tags: partitions
---


# Question
Title: Linear programing, objective function. variable depending on the sign of another variable
I have the variable Si. How to express a variable Di in LP that satisfies:

* `Di=100*Si` if `Si>=0`
* `Di=-200*Si` if `Si<0`

The objective function would be `Min{Sum(Di)}`

# Answer
I think it's cleaner to define two variables that represent the positive and negative parts of `Si`. Call them `Si1` (= positive part) and `Si2` (= negative part).

```
Si1 - Si2 = Si
Si1, Si2 >= 0

```

---

Probably you will also need constraints that say that if `Si < 0` then `Si1` *must* equal 0, and if `Si > 0` then `Si2` *must* equal 0. Introduce an additional binary variable `y` that equals 1 if `Si > 0`, equals 0 if `Si < 0`, and could equal either if `Si = 0`:

```
-M * (1 - y) <= Si
 M * y >= Si

```

where `M` is a large constant. Then require `Si1 = 0` if `y = 0` and `Si2 = 0` if `y = 1`:

```
Si1 <= M * y
Si2 <= M * (1 - y)

```

Then set your objective function to `minimize 100 * Si1 + 200 * Si2`.

---

**Note:** If both `Si1` and `Si2` have positive coefficients in the objective function, and the objective is a minimization, then you do *not* need the stuff after the divider line. The two constraints before the line are sufficient, because we will always want to set `Si1` and `Si2` as small as possible, which means setting one of them to 0.
> 2 votes

---
Tags: linear-programming
---


title: Questions about Turing Machine

text:
# Question
Title: Questions about Turing Machine
Below I will list a concrete example and the confusion it causes.

Let's first say we have a decision problem, which is:

"Is X \<= 400?"

We define the alphabet as the set of natural numbers.

The language formed by this problem is $L = \\{ w | w \<= 400 \\}$

We define a Turing machine, M, over the alphabet, that halts in an accepting state on any word that is in L. Ie the Turing machine recognises L.

$L(M) = \\{ w |$ M halts in an accepting state on input w$\\}$

* Am I correct in saying that, we do not know whether this Turing machine will halt for any given input?
* Since this is a decision problem, the language realised from it, will always b finite?
* Am I correct in saying that we have defined this Turing machine to accept one word at a time, where the words are numbers. We could have made it accept two words, if the algorithm was modified to accept two inputs.
* How would the Language be for the problem: "Is X \<= Y?"
* For a decision problem, the elements in the Language realised are the solutions?

+ I left out the notion of an algorithm, in my explanation, Is it not needed as it is implicit in the Turing machine halting on any input of L? Which means it implements some algorithm that can solve the problem?

# Answer
> We define the alphabet as the set of natural numbers.

No you don't. The alphabet must be finite.

> Am I correct in saying that, we do not know whether this Turing machine will halt for any given input?

If all you know is that the TM recognizes the language then you're correct: it could loop forever on some inputs.

> Since this is a decision problem, the language realised from it, will always b finite?

That doesn't follow from being a decision problem. This language is finite because there are only finitely many natural numbers less than 400. But, for example, the language of even numbers is infinite, but it's still a decision problem.

> Am I correct in saying that we have defined this Turing machine to accept one word at a time, where the words are numbers. We could have made it accept two words, if the algorithm was modified to accept two inputs.

Yes, you could produce a Turing machine that decides the language $\\{x,y\mid x,y\leq 400\\}$.

> How would the Language be for the problem: "Is X \<= Y?"

It would be the set of all strings with that property.

> For a decision problem, the elements in the Language realised are the solutions?

I'm not sure what you mean by "realised". (You wrote it before but the exact meaning wasn't so important, then.) A decision problem is any problem of the form "Does the input string have property X?" and it's naturally associated with the language of strings that do have that property.
> 3 votes

# Answer
Let me start with a small but important point. You need to distinguish between $X$ which is a natural number and $w$ which is a string representing a natural number. So the string $11$ could represent the number $2$ in unary, the number $3$ in binary, the number $11$ in decimal, the number $17$ in hexadecimal etc. The language

$L=\\{w|w \text{ represents a natural number } X \le 400\\}$

will depend on how you want to represent numbers.

Second point - we can create a finite state automata $F(L)$ that recognises $L$. For example, if we are using the unary number system then $L$ consists of all strings of $1$s with length no greater than $400$, so a $402$ state DFA with $400$ accepting states will recognise $L$.

There will be many different Turing machines $M(L)$ that accept $L$. And it is certainly possible to design a convoluted and highly obfuscated such $M(L)$ for which it is impossible to determine whether it halts for certain inputs.

But since we know there is a finite state automata $F(L)$ that accepts $L$, the most straightforward approach is to implement this automata as a Turing machine $M(F(L))$. And with this approach, we can be sure that $M(F(L))$ will always halt on any given input $w$ because $F(L)$ will go through at most $|w|$ state transitions.

To capture the decision problem "Is $X \le Y$" as a language, you simply need to devise a scheme for representing two natural numbers $X$ and $Y$ in a single word. A simple way to do this is to introduce a symbol $\\#$ that is used solely for separating numbers (or, strictly speaking, representations of numbers). Then you can then define the language

$L' = \\{x\\#y| (x \text{ represents a natural number } X) \land (y \text{ represents a natural number } Y) \land (X \le Y)\\}$
> 1 votes

---
Tags: turing-machines
---


# Question
Title: How do I prove no algorithm exists for a given problem?
Is there a general framework for showing that a problem has no algorithm? For example, to show that two problems are equally as hard to each other, we use reduction.

One example of where this was done, is Hilbert's 10th problem

# Answer
> 2 votes
The term or tag you are looking for is "undecidability" or "computability". The basic version of the theory of undecidability is a part of the theory of computation, which is an ingredient of the curriculum of all students majoring in Compute Science, as far as I know.

You can search for "undecidability" or "halting problem", the most famous and the most canonical problem that cannot be solved by an algorithm, in your textbook or course material. Or right here. There are also much stuff around.

---
Tags: complexity-theory
---


# Question
Title: Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor
I was trying to solve the following question while reviewing master theorem.

Which of the following asymptotically grows faster.

(a) $ T(n) = 4T(n/2) + 10n $

(b) $ T(n) = 8T(n/3) + 24n^2 $

(c) $ T(n) = 16T(n/4) + 10n^2 $

(d) $ T(n) = 25T(n/5) + 20(n\log n)^{1.99} $

(e) They are all asymptotically the same

My calculation says, (a) is $\theta(n^2)$ (b) is $\theta(n^2)$ (c) is $\theta(n^2\log n)$. Now how can I evaluate (d)?

If $f(n)$ is smaller or larger than $n^{\log\_b a}$by less than a polynomial factor, how can I solve $T(n)$?

# Answer
> 0 votes
> $ T(n) = 25T(n/5) + 20(n\log n)^{1.99} $

Note that $(\log n)^m=O(n^\epsilon)$ for all $m,\epsilon\in \Bbb R^+$. In plain words, all polynomials of $\log n$ grows slower asymptotically than all polynomials of $n$. Here we abuse "polynomials" to include functions like $x\to x^k$ for all $k\in\Bbb R^+$ such as $x\to x^{0.618}$ or $x\to x^{2019.46}$. This abuse of the term "polynomial" is common when we are talking about the asymptotic behavior of functions.

In particular, $(\log n)^{1.99}=O(n^{0.005})$.

Since $(n\log n)^{1.99}=n^{1.99}(\log n)^{1.99}= O(n^{1.995})=O(n^{log\_525-0.005})$, you can apply the case 1 of Master theorem. $T(n)=\Theta(n^2)$.

---

If $f(n)$ is indeed smaller or larger than $n^{\log\_b a}$by less than a polynomial factor, then we are running into the cases strictly between case 1 and case 2 or between case 2 and case 3. The master theorem you were reviewing cannot be applied any more.

You may look into this answer that handles some of those situations.

---

**Exercise.** Show that $(\log n)^m=O(n^\epsilon)$ for all $m,\epsilon\in \Bbb R^+$. (For example, $(\log n)^{10000000}=O(n^{0.000001}).$)

---
Tags: asymptotics, master-theorem
---


# Question
Title: Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)
I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially taking exponential time (2^P(n) where P is polynomial).

Moreover, can it be generalised to EXPTIME in general?

The reason I am asking this is that I wrote some programs to solve degenerate cases of an NPC problem, and they can consume very large amounts of RAM for hard instances, and I wonder if there is a better way. For reference see https://fc-solve.shlomifish.org/faq.html .

# Answer
Generally speaking, the following is true for any algorithm:

1. Suppose $A$ is an algorithm that runs in $f(n)$ time. Then $A$ could not take more than $f(n)$ space, since writing $f(n)$ bits requires $f(n)$ time.
2. Suppose $A$ is an algorithm that requires $f(n)$ space. Then in $2^{f(n)}$ time, $A$ can visit each of its different states, therefore can gain nothing by running more than $2^{f(n)}$ time.

It follows that:

> $\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

The statemement is known as part of the relations between the classes, as depicted by the following diagram:

The explanation is simple: a problem $Q$ $\in$ $\mathbf{NP}$ has a polynomial length certificate $y$. An algorithm that tests all possible certificates is an algorithm that decides $Q$ in time $\large 2^{n^{O(1)}}$.

Its space requirement is:

* $y$ (polynomial in $n$)
* space required to verify $y$. Since $y$ is a polynomial certificate, it can be verified in polynomial time, hence cannot possibly require more than polynomial space.

Since the sum of two polynomials is also a polynomial, $Q$ can be decided with polynomial space.

---

**Example:**

Suppose $\varphi$ is an instance of 3-CNF on literals $x\_1 \dots x\_n$, with $m$ clauses. An assignment $f$ is some function $f:\\{x\_1\dots x\_n\\} \rightarrow \\{0,1\\}$.

It holds that:

* There are $2^n$ different assignments.
* Given an assignment $f$, it takes $O(m)$ time to calculate the value of $\varphi$, therefore it cannot require more than $O(m)$ space.

So an algorithm $A$ that checks all possible assignments will use polynomial space, run in exponential time and decide 3-SAT.

It follows that:

3-SAT $\in \mathbf{PSPACE}$, and since 3-SAT is NP-Complete, $\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$
> 27 votes

# Answer
Yes. Here's a sketch of a direct proof.

If a problem is in $\mathrm{NP}$, there is a nondeterministic Turing machine $M$ that decides it, and there's a polynomial $p$ such that none of $M$'s computation paths on inputs of length $n$ take more than $p(n)$ steps. That means that a single path can't use more than $p(n)$ tape cells, so we can simulate a single path deterministically in polynomial space.

But we need to simulate *all* the paths. Well, there is a constant $c$ that depends only on the transition function of $M$ (and not on its input) such that $M$ has at most $c$ nondeterministic choices at any step. That means that there are at most $c^{p(n)}$ different computation paths for any input of length $n$. We can simulate all of these $c^{p(n)}$ paths as follows. First, write out a $p(n)$-digit number in base-$c$ (this takes space $p(n)$ but that's polynomial, so it's OK). Then, simulate the operation of $M$ and, at the $i$th step of the computation, use the $i$th digit of the number to decide which nondeterministic choice to make. If, for example, the $i$th digit is $6$ and there are only four choices that can be made, abandon that simulation and go on to the next one.

So, now, to do the whole simulation, we start by writing out the number $0\dots 0$, simulate that path of $M$, increment the number, simulate the next path, and so on, until we reach the number where every digit is $c-1$. We've now simulated every possible computation path, and we've done it in time about $c^{p(n)}p(n)$, using space about $2p(n)$. That's exponential time and polynomial space, as required.
> 9 votes

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


# Question
Title: Why do we use worse-case when categorising problems?
Maybe I am wrong, but I read that when we categorise problems in their respective complexity classes, we use worse-case analysis.

Why don't we use the average case?

I imagine we could have a problem in NP when we look at it's worse-case, but when we look at it's average-case we could have a really efficient algorithm. This is just intuition and not sure of an example.

For something like cryptography, I'm guessing this is not desirable.

# Answer
Because average case requires a definition of "average". Specifically, average over what distribution of inputs?

Worst-case does at least give you an objective guarantee: whatever input you consider, it won't be worse than this. That sort of guarantee still has some value even if the worst-case inputs aren't representative of what you're going to be doing.

On the other hand, average-case doesn't necessarily correspond to anything very much. Suppose you just take the uniform distribution over inputs of a given length. Why would you feel that the mean number of steps the algorithm takes is a useful measure of anything? Probably your inputs don't look much like a uniform distribution. The mean based on any distribution doesn't give you any guarantees about actual performance on specific instances.

Also, and this might, sadly, be the real reason, average-case complexity is *hard*. It means you have to understand how the algorithm behaves on essentially all possible inputs, and getting good bounds for all kinds of input is a lot of work.

One place where average-case is used is amortized analysis. Consider a dynamically sized hash table where, if the table is more than, say, three-quarters full, you copy everything into a new table that's double the size. In this situation, inserting an element into a table of size $n$ can take up to $2n$ steps, which is horrible in the worst case. However, you only need to do this expensive copying operation once every $3n/4$ steps. On average, then, each insert operation causes $2n/(3n/4)=8/3$ amount of the work needed to double the size of the hash table. So, in a very strong sense, the average cost of growing the table is just a constant amount per insertion, and this is completely independent of what insertions are done. This is practically very useful when analyzing algorithms that use hash tables.
> 4 votes

# Answer
If you want to categorize a problem in a way that makes it comparable to other problems, then you need to categorize it the same way as everyone else does.

If you are only interested in one particular problem, then you can analyze it any way you like. You might look at the worst case, or the average case, or you can analyze "typical" cases, whatever "typical" means. For example, for NP-complete decision problems you often have instance where the answer isn't just "Yes" or "No" but "obviously yes" or "obviously no", and these instances may be easy to solve, even though the problem is NP complete. And the instances that you usually encounter might fall into the "easy" cases.

Note that "average" may be very hard to define.
> 1 votes

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


# Question
Title: How much can we trust mathematical software when working with large numbers, and how much memory it needs to work with these numbers?
For example, I want to evaluate the expression:

$3^{3^{{3}^{3}}}$

so I used wolframalpha.com (it's free, and I don't own any software), which returned the scientific notation of the number above, namely:

$ 1.258014290627491317860390698... × 10^{3638334640024}$

Which is *huge*. However, for the number below

$4^{4^{{4}^{4}}}$

Wolfram can't return a scientific notation, probably because it's a *much larger* number and it needs a lot of memory.

> Questions: a) How much can we trust that

$3^{3^{{3}^{3}}} \approx 1.258014290627491317860390698... × 10^{3638334640024} $

> b) how much memory (aproximate) it needs to evaluate

$3^{3^{{3}^{3}}}$

and

$4^{4^{{4}^{4}}}$

I'm guessing a lot of terabytes and something that a home computer can't handle. But for the first number, Wolfram can, and the second number, it can't. How do we even find how much size we need to calculate these numbers?

# Answer
Question a):

Here is the output from python console.

```
>>> import math
>>> math.log(3,10) * (3**(3**3))
3638334640024.0996
>>> math.pow(10, 0.0996)
1.2577664324512539

```

The first 5 most significant digits are almost the same of that of Wolfram, 12577 vs 12580.

If we try the following at my favorite online arbitrary precision calculator,

```
pow(3.0000000000000000000000000000000, pow(3, pow(3, 3)))

```

we get

```
1.2580142906274913178603906982032e3638334640024

```

which is completely consistent with Wolfram. So Wolfram can be fully trusted on this particular result.

You might be wondering why "$3.000000$$000000$$000000$$000000$$0000000$" is entered instead of a simple "$3$". Had "$3$" been used, that calculator would have performed integer calculations without loss of precision, which will run out of 30-second time limit in our case. "$3.0$" would be enough to instruct that calculator to use floating numbers, which, however, would have only 2 digits of precision. That long string of 0s is used to specify 32 digits of precision of floating-point numbers.

---

Question b):

The computation above showed there are 3638334640025 digits if we express $3^{3^{3^3}}$ as a decimal integer. It we store 2 digits in one 8-bit byte, we need 1.82 terabyte storage.

However, if we ask that online calculator to compute $4^{4^{4^4}}$,

```
pow(4.0000000000000000000000000000000, pow(4, pow(4, 4)))

```

it say,

```
Complete loss of accurate digits

```

That is not a surprise since the exponent $4^{4^4}$ $=$ $1340780792994259$$7099574024998205$$8461274793658205$$9239337772356144$$3721764030073546$$9768018742981669$$0342769003185818$$6486050853753882$$8119465699464336$$49006084096$ $\approx$ $1.34×10^{154}.$ We can work around this out-of-limit error by computing directly the exponent of 10 in $4^{4^{4^4}}$ by using $\log$ with base 10.

```
log(4.0000000000000000000000000000000,10) * pow(4, pow(4, 4))

```

The answer is

```
8.0723047260282253793826303970853e153

```

That number of digits, about $8\times10^{153}$ is much more than vigintillion in long scale. To store $4^{4^{4^4}}$ as a decimal integer, it is not enough even if all atoms in the known universe are used, assuming each of them can store more digits than all available computer storage on earth.

However, not a lot of memory is needed for the calculations above to obtain the result above. It is possible that a few megabyte or just several kilobytes of extra memory could support the calculations above.
> 2 votes

# Answer
Compute `4^4^4` and you will know how much pairs of bits `4^4^4^4` will require to represent.
> 1 votes

---
Tags: floating-point, number-formats, numerical-analysis, numeral-representations, mathematical-software
---


# Question
Title: Heuristics vs meta-heuristics vs hyper-heuristics?
The wikipedia page on **meta**-heuristics states that they are "heuristics designed to find, generate, or select a heuristic".

The wikipedia page on **hyper**-heuristics states that they are "heuristic search methods that seeks to automate \[...\] the process of selecting, combining, generating or adapting several simpler heuristics".

Moreover, it also states that "The fundamental difference between **metaheuristics** and **hyper-heuristics** is that most implementations of metaheuristics search within a search space of problem solutions, whereas hyper-heuristics always search within a search space of heuristics."

**This leaves me confused**: it seems like the hyper heuristic page is contradicting the meta-heuristic page. How can a meta-heuristic search for heuristics, if its search space is the problem space rather than the space of heuristics?

**What really is the difference between metaheuristics and hyperheuristics?**

# Answer
> 1 votes
Defining meta-heuristics as "heuristics designed to find, generate, or select a heuristic" seems too broad. A meta-heuristic is commonly understood as an algorithmic template that defines how different low-level heuristic components (e.g. constructive procedures, local searches, solutions recombinations) interact in the search. After instantiating these components for a specific problem, you get a heuristic which searches in the solution space.

Gendreau, Potvin, Handbook of Metaheuristics define them as

> solution methods that orchestrate an interaction between local improvement strategies and higher-level strategies to create a process capable of escaping from local optima and performing a robust search of a solution space

and chapter "Defining the term 'Metaheuristic'" of Zäpfl, Braune, Bögl, Metaheuristic Search Concepts summarizes

> * A metaheuristic relies on a *high-level strategy* which builds upon a particular basic search principle
> * The high-level strategy is *problem-independent* and can be seen as an abstract framework
> * The high-level strategy has to properly realize a balance between the two forces *intensification* and *diversification*.

Thus, a short answer could be: **in a meta-heuristic the designer instantiates low-level heuristics; a hyper-heuristic automates the selection or generation of the low-level heuristics**.

---
Tags: optimization, heuristics, search
---


# Question
Title: Why do P-class problems not require a witness like NP?
If I am given a problem in P, to claim that I have solved it, I would need to give proof, right? For example, to show a number is not prime, if I use some deterministic algorithm, I can return the prime factors of that number.

I am finding it weird that P does not require a witness/certificate in the definition like NP.

# Answer
> 1 votes
If we look at decision problems, then a problem is in P if for "YES" instances "I think the answer is YES" is a witness that can be checked in polynomial time :-)

# Answer
> 0 votes
This is basically a maybe more succinct version of gansher729's answer.

A language $L$ is in $\mathsf{NP}$ if for any input $x \in L$, you can find a witness, of polynomial in $|x|$ size, that can be checked in polynomial time. This is, "$x \in L$! Here is a proof, that you can verify in polynomial time."

A language $L$ is in $\mathsf{P}$ if for any input $x \in L$, you can find a witness, of size $1$, that can be checked in polynomial time. This is, "$x \in L$! I do not give you a proof, but you can find one yourself in polynomial time."

---
Tags: complexity-theory
---


# Question
Title: Given a randomised algorithm for a problem, is there a corresponding deterministic algorithm?
Does every randomised algorithm have a corresponding deterministic algorithm solving the same problem?

I'm going to guess that the deterministic algorithm will take more time, while the randomised algorithm although it has errors will generally be faster. This is from what I have seen of them so far. Let me know if this is wrong.

# Answer
If the running time of the algorithm is bounded, in the sense that for every input $x$ there is a number $T(x)$ such that whatever the coin tosses are, the algorithm always terminates within $T(x)$ steps, then you can always "try all possibilities" and convert your randomized algorithm to a deterministic one, albeit with a possibly much larger running time.

For polynomial time algorithms in particular, it is conjectured that you can derandomize any algorithm with at most a polynomial blow-up in time, a conjecture usually stated as $\mathsf{P}=\mathsf{BPP}$.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Proving there is no polynomial algorithm for independent set
I need some guidance in an assignment I'm doing.

I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the same algorithm and it also guarantees that some inequality holds, which I also don't understand, since $A(G)$ returns the size of a maximal independent set in $G$ and $OBT(G)$ returns the size of an independent set of maximal size for $G$ but isn't the case that a graph could have multiple maximal independent sets? Let's assume that it returns the largest one which reduces the epression to $0 \le K$ which should always holds since $K$ is a natural number?

As for the hint given, I don't see how we can use $H$ if I understand it correctly, it says split $G$ into disjoint sets. Also it says for every instance $G$ which is confusing me.

When I asked the professor she was very reluctant to help me, so please any guidance is appreciated.

The full question: .

# Answer
> 1 votes
Suppose that there exists an integer $K$ and a polynomial time algorithm $A$ which, when run on a graph $G$, outputs a value $A(G)$ which satisfies $$ |A(G) - \alpha(G)| \leq K, $$ where $\alpha(G)$ is the maximum size of an independent set in $G$.

We will show that $A$ can be used to determine $\alpha(G)$ in polynomial time, which contradicts the assumption $\mathsf{P} \neq \mathsf{NP}$.

Given a graph $G$, let $H$ consist of $2K+1$ disjoint copies of $G$; note that $\alpha(H) = (2K+1) \alpha(G)$. Run $A$ on $H$ to get a value $A(H)$ which satisfies $$ |A(H) - \alpha(H)| \leq K \Longrightarrow |A(H) - (2K+1) \alpha(G)| \leq K \Longrightarrow \\ (2K+1)\alpha(G) \in \\{A(H)-K,\ldots,A(H)+K\\}. $$ The set on the right contains $2K+1$ values, exactly one of which is a multiple of $2K+1$, hence we can determine $\alpha(G)$ given $A(H)$.

---
Tags: complexity-theory, graphs, np, approximation
---


# Question
Title: Decisional problems vs Optimization problems : NP-COMPLETE vs NP-HARD
I'm studying some of computation theory and i encounter a big question mark. I have an optimization problem and i have to proof that is NP-HARD. I know that my problem can be reduced to another np-complete problem so my problem is np-hard. But my question is: why some algorithms are np-hard for the combinatorial version and the same problem transformed in a decision problem are np-complete?

I mean, if i have an optimization problem, is this np-hard because the decision problem can be reduced in a np-complete problem?

# Answer
> 5 votes
NP-hardness is a category that applies to both decision problems and optimization problems. In contrast, NP-completeness is a category that applies only to decision problems.

Here are the relevant definitions:

* A decision problem is in NP if it is accepted by some polynomial time nondeterministic Turing machine.
* A decision problem is NP-hard if all problems in NP can be reduced to it in polynomial time.
* A decision problem is NP-complete if it is both in NP and NP-hard.
* An optimization problem "max $f(x)$ subject to $x \in X$" is NP-hard if the decision problem "given $x$ and $y$, does there exist $x \in X$ such that $f(x) \geq y$?" is NP-hard.
* An optimization problem "min $f(x)$ subject to $x \in X$" is NP-hard if the decision problem "given $x$ and $y$, does there exist $x \in X$ such that $f(x) \leq y$?" is NP-hard.

The decision problems used to define NP-hardness for optimization problems are known as *decision versions* of the optimization problems.

One could extend the definition of NP to optimization problems in various ways. For example, we could say that "max $f(x)$ subject to $x \in X$" is in NP if its decision version is in NP. This would also allow us to define NP-completeness for optimization problems. But for some reasons these definitions are not standard.

Let me also mention FNP, an extension of NP to functions.

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


# Question
Title: 4-partition elements summation NP completeness
How can we prove that the following problem $A$ is NP complete?

Given a set of integers $S={a\_1, ..., a\_n}$ and a number $D$, is it possible to find disjoint sets $S\_1, S\_2, S\_3, S\_4$ such that $S\_1 \cup S\_2 \cup S\_3 \cup S\_4=S$ and

$$ -\sum\_{j=1}^{4}\frac{\sum\_{a\_i \in S\_j}a\_i}{\sum\_{a\_i \in S}a\_i}\log\_2(\frac{\sum\_{a\_i \in S\_j}a\_i}{\sum\_{a\_i \in S}a\_i})\geq D$$

I was thinking on using some NP complete problem $B$ and showing that $B \leq\_P A$, but I can't figure out what reduction would work.

Here is what I tried (simplified the problem to 2 sets): Given a set $S$ of n elements, I tried to prove that $S \in \text{Partition-Problem} \iff \langle S, 1 \rangle \in A$. If $S$ is an instance of the partition problem, it means there are 2 subsets in $S$ that have the same sum ($n/2$). Therefore the expression in $A$ (with 2 sets instead of 4) evaluates to $-\log\_2 (1/2)=1$. Then proving $S \in \text{Partition-Problem} \Rightarrow \langle S, 1 \rangle \in A$ is trivial. However I am still stuck at proving the $\Leftarrow$ part.

# Answer
> 1 votes
Let's say that the numbers $a\_1,\ldots,a\_n$ are non-negative, and sum to $A$. They induce a probability distribution on $\\{1,\ldots,n\\}$, in which the probability of $i$ is $a\_i/A$.

Given a partition $S\_1,S\_2,S\_3,S\_4$, let $I$ be a random variable distributed as above, and let $X$ be the index of the set to which $I$ belongs (so $X \in \\{1,2,3,4\\}$). Your condition then reads $$ H(X) \geq K, $$ where $H(\cdot)$ is the entropy function.

This suggests choosing $K = 2$, since we know that $H(X) = 2$ iff $\Pr\[S\_1\] = \Pr\[S\_2\] = \Pr\[S\_3\] = \Pr\[S\_4\]$.

We can now describe a reduction from PARTITION to your problem. Given an instance $b\_1,\ldots,b\_m$ of PARTITION, where $b\_1,\ldots,b\_m$ are non-negative integers summing to $B$, create an instance of your problem by adding two copies of $B/2$, and by taking $K=2$. The list $b\_1,\ldots,b\_m,B/2,B/2$ can be partitioned into four parts with equal sum (i.e., $H(X) \geq 2$) if $b\_1,\ldots,b\_m$ can be partitioned into two parts with equal sum.

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


# Question
Title: Set of steps that cannot be implemented on a Turing machine
Is there an example of a "set of steps" that we thought was an algorithm, but later was shown not to be an algorithm because it could not be implemented on a Turing machine?

# Answer
> 2 votes
The Church–Turing thesis states that every algorithm can be implemented on a Turing machine. It has stood the test of time. In particular, I believe that the answer to your question is negative.

The appearance of quantum algorithms, in particular Shor's factorization algorithm, has called into question the *efficient* Church–Turing thesis (sometimes known as the Cook–Karp thesis), which states that $\mathsf{P}$ captures the class of efficiently solvable problems; but quantum computers are known to compute the same class of languages as classical computers.

# Answer
> 2 votes
When Hilbert set out his famous list of problems in 1900, the tenth problem was posed as follows:

> "Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers"

This wording strongly suggests that Hilbert (and the majority of the mathematical community at that time) believed a "set of steps" existed that could solve any system of Diophantine equations, given enough time and resources. Hilbert's challenge was to "devise" i.e. to formally document this process in a "finite number of operations" - what in modern terms we would call an algorithm.

We now know that Hilbert's tenth problem is undecideable, and the general algorithm that Hilbert was asking for does not exist.

---
Tags: turing-machines
---


# Question
Title: Prove that the language L = {w1, w1w2, w1w2w3, ..} is regular, provided wi is in a regular language
Let's assume that we're working over a finite alphabet $\Sigma=\\{a, b\\}$. How can one prove that $$L\_2=\\{w\_1w\_2...w\_m| m ∈ \mathbb{N}, ∀i(w\_i ∈ L)\\}$$ is a regular language, provided that L is regular? By the way, L is a fixed language in the problem that I am solving, but it's regularity is trivial to prove so I have omitted it. This next step, however, I can't think of a valid way to prove. I would be glad if you guys could give me a hint.

# Answer
> 2 votes
Your language is known as $L^+$.

It is a very standard property of regular languages that if $L$ is regular then so is $L^\*$; this can be proved in several ways, and you can find proofs in textbooks and online sources. Since $L^+$ is either equal to $L^\*$ or obtained from it by removing $\epsilon$ (the empty string), then $L^+$ is also regular.

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


# Question
Title: Does a Non-Deterministic Turing Machine solve all problems in P in constant time?
If a non-deterministic Turing machine can just "guess" the correct answer to a problem, does it do this in constant time/immediately? Also, does this also apply to problems in NP too?

# Answer
A nondeterministic Turing machine can guess at most one bit each step — this is how they are defined. In particular, a nondeterministic Turing machine running in constant time can be converted to a deterministic machine also running in constant time. This should allow you to answer your own question.
> 4 votes

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


# Question
Title: Are Linear Bounded Automatons Turing Complete?
Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape.

But this causes them to not be Turing Complete? Why?

# Answer
A linear bounded automaton is a Turing machine that runs on input of size $n$ in $\mathcal{O}(n)$ space. By the space hierachy theorem there exist languages that need e.g. $\omega(n^2)$ space.
> 4 votes

# Answer
You know that Turing machines can accept languages that aren't recursive.

A linear bounded automaton (LBA) running on word $\omega$ has a *finite* tape at it's disposal, so the total number of configurations (tape contents, head position, state) is finite. For a given word $\omega$ you can go through all possible computations of the automaton (by the above, there is a finite number of computations that don't lead to loops) and check if it accepts or not. Thus LBAs accept only recursive languages. Turing machines are strictly more powerful.
> 2 votes

---
Tags: turing-machines, turing-completeness, church-turing-thesis, linear-bounded-automata
---


# Question
Title: How to calculate point in 3D space from multiple perspective
I have multiple camera in different points.

I have their position and rotation as $(x,y,z)$ , $(\alpha,\beta,\gamma)$ or $( roll, pitch, yaw)$ .

And I have output like this :

Feed from camera-1, I know length of yellow and green.

**How can I calculate position of the object, in this case head in 3D space.**

# Answer
> 1 votes
For each camera, you can compute the direction on which is detected the object. The position and orientation of the camera let you find the direction of the center of the image. Depending on camera aperture, each pixel of the image corresponds to a slightly different direction. I don't know which definition you use for your angle so I won't risk any expression of it but you should convert the angle to obtain a vector in cartesian coordinates.

So from a camera with position at $(x\_c, y\_c, z\_c)$ and detecting the object in the pixel of direction defined by the unitary vector $(x\_d, y\_d, z\_d)$, you know the object is along the direction:

($x\_c + x\_d \times d, y\_c + y\_d \times d, z\_c + z\_d \times d$) with $d$ being the distance camera-object.

Now if you have 2 cameras, you can look for the nearest points from each line to the other and take their center as position of the object (see skew lines).

---
Tags: computational-geometry, computer-vision
---


# Question
Title: Context free grammar for language with even number of $0$'s and $1$'s
I want to create a Context-Free grammar that generates the language

$$ L = \\{ w \in \\{0, 1\\}^\* |\ \text{number of $0$'s is even, and number of $1$'s is also even} \\}. $$

I came up with

$$ S \rightarrow 0S0S\ |\ 1S1S\ |\ ABABS\ |\ BABAS\ |\ \epsilon \\ A \rightarrow 0A0A\ |\ 1A1A\ |\ 0\\ B \rightarrow 0B0B\ |\ 1B1B\ |\ 1\\ $$

Looks like it does the job, but how can I be sure that it does indeed generate L.

Any help would be appreciated.

# Answer
> 3 votes
> how can I be sure that it does indeed generate $L$?

You should show both of the following. There are a variety of methods to choose. Mathematical induction or structural induction is usually involved.

* It generate every string in $L$.
* It does not generate any string that is not in $L$.

It turns out

* Your grammar does not generate 010001, a string in $L$. This non-generation is not hard to prove by hand, although it can take some time. Basically, you can make lots of small observations on the generation rules such as $A$ becomes either 0 or at least 4 symbol long. There are also efficient algorithms to compute whether a string can be generated by a given context-free grammar.
* Your grammar generates 1010000, which is not in $L$.
    + $A\Rightarrow 0A0A\Rightarrow^\*0000$.
    + $S\Rightarrow BABAS \Rightarrow^\* 101A\Rightarrow^\*1010000$

---

It looks like that some of the common/basic intuition to create context-free grammars (CFG) or regular grammars might be helpful for you.

* Each of the non-terminals in a CFG stands for a context-free language. Try to formulate each of them in plain English (or in your favorite model). Try to describe each rule in plain English as well.
* There are some basic tools you would like to know.
* If the conditions on the strings can be computed in bounded memory, then the language is regular. In the current case, $L$ is a regular language since there are only finitely many combinations of the number of 0's in a string modulo 2 and the number of 1's in it modulo 2. In fact, there are only $2\times2=4$ combination.

---

Let $E\_s$ be the language of words that are **e**quivalent to the string $s$ where a string $w$ is equivalent to $s$ if the number of 0's or 1's in $w$ is of the same parity as the number of 0's or 1's in $s$, respectively. For example, since there is an odd number of 0's and an even number of 1's in string $0$, $E\_0$ is the language of words with an odd number of 0's and an even number of 1's.

It is easy to construct the following grammar that can be proved easily to generate the given language, where $E\_s$ is abused as a non-terminal for $s=\epsilon, 0,1,$ and $01$ with $E\_\epsilon$ viewed as the starting symbol.

$$\begin{array}{lllllll} E\_\epsilon &\to &0E\_0 &\mid &1E\_1 &\mid &\epsilon\\ E\_1 &\to &0E\_{01} &\mid &1E\_\epsilon &\\ E\_0 &\to &0E\_\epsilon &\mid &1E\_{01} &\\ E\_{01} &\to &0E\_1 &\mid &1E\_0 &\\ \end{array}$$

**Exercise.** Write a grammar for $\\{ w \in \\{0, 1\\}^\*$ | the difference of the number of 0's in $w$ and the number of 1's in $w$ is odd $\\}$.

# Answer
> 2 votes
The most common approach to show that two sets are the same is to show that they are subsets of each other.

In this case, that means (1) every string with an even number of $0$s and $1$s has a derivation in the grammar, and (2) every derivation of the grammar has an even number of $0$s and $1$s.

In attempting (2), a reasonable approach is to prove inductively, from smaller strings to bigger strings.

For example, considering $S \to 0S0S$, since the number of $0$s increases by 2 and the number of $1$s stays the same, the resulting string has the desired property when the smaller $S$ strings in the right hand side do.

However, I think you'll find the $S \to BABAS$ case hard to prove correct, which suggests that's where you need to look for a counterexample. Indeed, here's one:

```
0101010 = (B:0)(A:1)(B:0)(A:1010)(S:) = (B:0)(A:1)(B:0)(A:(1(A:0)1(A:0)))(S:)

```

# Answer
> 2 votes
The non-terminals we'll write $\[xy\]$ with $x = 0$ for an even number of $0$, $x = 1$ for odd number of $0$, similarly $y$ for $1$s. Set up so that $\[xy\]$ generates strings with the required parities: You get an odd number of $0$ by an even number of $0$ and an additional $0$, and so on. The grammar is then:

$\begin{align\*} \[00\] &\to \[10\] 0 \mid \[01\] 1 \mid \epsilon \\ \[01\] &\to \[11\] 0 \mid \[00\] 1 \mid 1 \\ \[10\] &\to \[00\] 0 \mid \[11\] 1 \mid 0 \\ \[11\] &\to \[01\] 0 \mid \[10\] 1 \end{align\*}$

Rename the non-terminals as letters, and you are done.

Note that this grammar is regular, you can get a finite automaton for this (regular) language.

Don't overthink!

---
Tags: context-free
---


title: Prove that this language is NP-Hard

text:
# Question
Title: Prove that this language is NP-Hard
Given
$$\mathrm{\\#3SAT} = \\{ (w, y) \mid w\text{ is a $\mathrm{3SAT}$ instance with at least $y$ satisfying assignments}\\}\\,,$$ prove that $\mathrm{\\#3SAT}$ is NP-Hard.

I am currently stuck with this one.

Basically $\mathrm{\\#3SAT}$ is the counting version of $\mathrm{3SAT}$ and to me it is seems clear that establishing membership in the language is more complex than establish the classic $\mathrm{3SAT}$ membership.

I'm trying to reason through the prover-verifier paradigm: let's say you have a $\mathrm{3SAT}$ instance, now suppose the certificate for that instance is $n$ bits. It is obvious that the certificate for the same instance but translated into $\mathrm{\\#3SAT}$ with let's say $y=10$ would be at least $10n$ bits. So if the first can be examined in time $t$ then the second will take at least $10t$ and so on. However I am not satisfied with this reasoning, it seems incomplete and superficial. I would greatly appreciate your advice on how to proceed with this proof. Thanks in advance.

# Answer
> 3 votes
It seems that you're trying to prove that $\\#\mathrm{3SAT}$ is in $\mathrm{NP}$. Since $\\#\mathrm{3SAT}$ is $\mathrm{\\#P}$-complete, and $\mathrm{\\#P}$ seems to be harder than anything in the polynomial hierarchy, it's very unlikely that $\\#\mathrm{3SAT}\in\mathrm{NP}$.

The error in your attempted proof is that your certificate doesn't have polynomial length. A satisfying assignment has length $\Theta(|x|)$ (the formula can't have more variables than its length, but it could be of the form $(x\_1\lor x\_2\lor x\_3) \land (x\_4\lor x\_5\lor x\_6) \land\dots$). The number $y$ could have any value between zero and $2^{|y|}-1$, so your certificate has length about $|x|2^{|y|}$, which is exponential in the input size.

However, the question asks you to prove that it's $\mathrm{NP}$-hard, not that it's $\mathrm{NP}$-complete. You just need to prove that there's a polynomial-time reduction from some $\mathrm{NP}$-complete problem to $\\#\mathrm{3SAT}$.

# Answer
> 3 votes
The subset for $y = 1$ is 3SAT, which is NP-complete (thus NP-hard); the full set can't be easier...

---
Tags: np-hard, satisfiability, counting
---


# Question
Title: $NL^2 = NDSPACE(\log^2n)$ is closed under complement
* From Savitch's theorem we have $NL^2 \subseteq L^4$, which is deterministic and thus closed under complement.
* From Immerman–Szelepcsényi theorem we have $NL = coNL$.

Why then $NL^2 = coNL^2$

# Answer
> 2 votes
The Immerman–Szelepcsényi theorem states that $\mathsf{NSPACE}(s(n))$ is closed under complementation whenever $s(n) \geq \log n$.

---
Tags: complexity-theory, space-complexity
---


title: Help: Context Free Grammar

text:
# Question
Title: Help: Context Free Grammar
Construct the CFG given the following language:

$$\\{a^i \\; b^j \\; c^k \\;|\\; i = j \\; or \\; j = k \\}$$

# Answer
> 0 votes
The answer should be the following:

$$ \begin{align} &S \to WQ \mid XY \\ &W \to aW \mid ε \\ &Q \to bQc \mid ε \\ &X \to aXb \mid ε \\ &Y \to cY \mid ε \end{align} $$

# Answer
> 0 votes
Hint: Set up a grammar to get $i = j$ or $j = k$, then tweak to make sure the equality can't hold.

---
Tags: context-free
---


title: Logical characterization of $NC^1$

text:
# Question
Title: Logical characterization of $NC^1$
Morioka in his 2005 dissertation \[1\] referenced "On Uniformity within $NC^1$" by Barrington, Immerman, and Straubing. Using the following statement:

> Every $\mathbf{NC^1}$-predicate is computed by a Dlogtime-uniform family of polynomial-size propositional formulas

This sentence is essential to defining a reduction from an $\mathbf{NC^1}$ function to the $\Sigma\_1^q$-witnessing problem for $G\_0$, however I'm not able to understand how this statement was reached from the original paper, either I'm missing something important here or my expertise in circuit complexity is just not enough, can someone intuitively explain how this sentence came to be?

# Answer
> 1 votes
Morioka considers uniform versions of his circuit classes:

> Throughout this paper we write $\mathbf{NC^1}$ to mean $\mathbf{Dlogtime}$-uniform $\mathbf{NC^1}$, which is equivalent to the class $\mathbf{Alogtime}$ of languages accepted by an alternating Turing machine in $O(\log n)$ time.

The paper you mention should imply the equivalence of these two definitions. The statement you quote, however, is just true by definition.

---
Tags: complexity-theory, circuits, first-order-logic
---


title: Reducing 3 SAT to 3 SET PACKING

text:
# Question
Title: Reducing 3 SAT to 3 SET PACKING
I'm trying to prove NP-hardness of 3 SET PACKING, which is a following problem: given a family of sets where each set contains 3 elements, decide whether the family contains k sets that are pairwise disjoint.

I tried reducing 3 SAT, but to now avail, but reduction of any other NP-complete problem would be helpful.

# Answer
Your problem is known as 3-dimensional matching, or 3DM. It is one of the 21 problems proved to be NP-hard in Karp's original paper (number 17 on his list).
> 2 votes

---
Tags: np-complete, reductions, np-hard, np, packing
---


# Question
Title: Is there any relationship between time complexity and space complexity of an algorithm?
For example:

If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1)

Is there a way to increase the space complexity to something like O(n^2) that would guarantee that the time complexity would decrease?

# Answer
> If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1)

First of all we do not know any *exponential* or *sub-exponential time* algorithm that requires only $O(1)$ space, having said this, it is difficult to reason about a hypothetical algorithm "*A*" because the spatial and temporal complexity are closely linked to the functioning of the algorithms and are (generally) proportional to each other, however, the answer to your question is no.

Let's try to reason starting from a $3SAT$ instance. Now we know that $3SAT$ is ***NP-Complete*** (best known time complexity for $3SAT$ is currently $O(k^n)$ with $ K=1.439$ for a deterministic algorithm) and $3SAT$ $∈$ ***PSPACE*** , in fact space complexity of $3SAT$ is $O(n)$. Now it is difficult to imagine how increasing the space to a constant $k$ (in your question $k = 2$) may lead to a decrease in the execution time of the algorithm that solves $3SAT$ ... in fact always keep in mind that an increase in space also corresponds to a proportional increase over time. Let me conclude by recalling the relationships between temporal and spatial complexity classes for which we believe all inclusions to be strict:

$L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE$
> 1 votes

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


# Question
Title: Assigning $m$ balls to $n$ buckets - recursive algorithm
I came across the following problem and the answer to that problem:

> Given $m$ balls and $n$ bins, find out how many ways to assign the balls to the bins. Notice the bins have no order: for example, $(1,2,3)$ and $(3,2,1)$ are considered the same.
>
> As an example, if $m = 3$ and $n = 2$, you should return 2, since there are two possibilities: $(1,2)$ and $(3,0)$.

Here is a recurrence which seems to work: $$ f(m,n) = \begin{cases} 1 & \text{if } m = 0 \text{ or } n = 1 \\ f(m,m) & \text{if } n \> m \\ f(m,n-1) + f(m-n, n) & \text{if } 1 \< n \leq m \end{cases} $$

This solution seem to work. However I don't understand how $f(m,n-1) + f(m-n,n)$ works. Why is it considering $m-n$ balls into $n$ bins?

# Answer
> 1 votes
An assignment of balls into $n$ bins falls into either one of the following two cases.

* Every bin has as last one ball. So let us assign one ball to each bin first. What remains to do is to assign the remaining balls to the bins.
* Otherwise. That is, there is at least one bin that has no ball. This case is the same as assigning all balls into $n-1$ bins.

**Exercise.** Verify that we are counting without duplicates and without missing assignment.

---
Tags: recursion, balls-and-bins
---


# Question
Title: Given price and number of pages of each book, What is the maximum number of pages you can buy?
You are in a book shop which sells n different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.

Example:

```
In:
4 10
4 8 5 3  //price
5 12 8 1 //pages
Out:
13
Explaination: You can buy books 1 and 3. Their price is 4+5=9 and the number of pages is 5+8=13

```

This is my recursive approach :

f(i,j) is max pages, when you can afford i units of money and j is the index in vector uptill the jth book. ie 0 to jth books are considered.

```
f(x, 0)=max( f(x-price[indx], indx+1) + pages[indx], f(x,indx+1) );

```

I am having difficulty making the base case, what should be the base case?

Thank you.

# Answer
> 1 votes
I am afraid that the following recurrence equation as in the question is incorrect.

```
f(x, 0) = max( f(x-price[indx], indx+1) + pages[indx], f(x,indx+1) )

```

---

Let `g(i,j)` be the maximum number of pages possible when you have `i` units of money to spare and books `0..j` available to select, where `0..j` means 0, 1, ..., and `j`. (I use `g` instead of `f` since I am not absolutely sure of the definition of `f` in the question. It looks like `g(i,j)` should be the same as `f(i,j)` in the question. )

Here is the recurrence equation.

```
g(x, indx+1) = ( x >= price[indx+1] ) ?
              max( g(x - price[indx+1], indx) + pages[indx+1], g(x,indx) ) :
              g(x, indx)

```

In plain words, there are (at most) two possibilities when books `0..(indx+1)` are available to select.

* Book `indx+1` is selected (when `x >= price[indx+1]`). You have `pages[indx+1]` more pages.

Then you are left with `x - price[indx+1]` units of money and books `0..indx` to select.
* Otherwise.

Then you are left with `x` units of money and books `0..indx` to select.

Note that the available books on the right-hand side of the equation are always less than the available books on the left-hand side. That reduction of a larger problem to a smaller problem signifies the power of recursion.

The base case are when no books are available, i.e., `g(i,0) = 0` for all `i`, and when there is no money to spare, i.e., `g(0, j) = 0` for all `j`.

---
Tags: dynamic-programming, recursion
---


# Question
Title: Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?
In *Introduction to Automata Theory, Languages, and Computation*, John Hopcroft mentioned\[1\]

> In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is surprisingly complex.

How to prove that?

In contrast, is there a language that is accepted by some DPDA but can't be accepted by any non-deterministic one counter machines?

### Reference

\[1\]: John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2006). *Introduction to Automata Theory, Languages, and Computation*. Boston/MA: Addison Wesley. P359.

# Answer
> 3 votes
The conclusion is: the languages recognized by DOCA(deterministic one counter automata) is a **proper subset** of the languages recognized by DPDA(deterministic pushdown automata).

---

The reason why Hopcroft said the proof is complex is that in his definition, the input string of DOCA is appended with an *endmarker* \\$ \[1:P356\]. So, the actual difficulty is to prove that: for any language $L$, there exists DPDA $P$ s.t. $L = L(P)$ $\Leftrightarrow$ there exists DPDA $P$ s.t. $L\\$ = L(P)$.

This is shown in Exercise 8.5.2 \[1:P362\] .But I failed to prove the exercise by Hopcroft's hint. I find a detailed proof here by Hendrik Jan Hoogeboom and Joost Engelfriet \[2, see remark end of Section 1.6\].

Since, we can prove that the languages of DOCA is a subset of the languages of DPDA.

---

In contrast, $\\{ a^n b^m a^m b^m | n, m \ge 1 \\}$ is a language that can be recognized by some DPDA but can't be recognized by any DOCA. (Thanks to @Vor in his answer)

### References

\[1\] John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2006). *Introduction to Automata Theory, Languages, and Computation*. Boston/MA: Addison Wesley.

\[2\] H.J. Hoogeboom, J. Engelfriet (2004). *Pushdown Automata*. Chapter in: Formal Languages and Applications, C. Martín-Vide, V. Mitrana, G. Paun, eds. Springer.

---
Tags: formal-languages, automata, context-free, pushdown-automata
---


# Question
Title: Thorup : What is the meaning of super distance?
While reading Thorup's Algorithm to solve SSSP problem, I have one point that I can't understand: super distance.

It says: "For each vertex we have a super distance $D(v)\geq d(v)$"

$d(v)$ must refer the shortest distance from origin to $v$, but what is $D$ ?

Is it just a distance value from origin while calculation until $D(v)=d(v)$ ?

# Answer
> It says: "For each vertex we have a super distance $D(v)\geq d(v)$"

"Super" refers to the "$\ge$" relation between $D$ and $d$. In other words, since $D(v)\ge d(v)$ where $d(v)$ is the distance from $v$ to $s$, $D(v)$ is called super distance.

> Is it just a distance value from origin while calculation until $D(v)=d(v)$ ?

Correct. It is just a distance that approximates the shortest distance from the source from above, which will become that shortest distance at the time $v$ is moved to $S$, the set of vertices whose distances have been settled.
> 1 votes

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


title: DSPACE(f(n)) closed under complement

text:
# Question
Title: DSPACE(f(n)) closed under complement
I think you can create the complementary language that is an element of **DSPACE**($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$ does not change, therefore **DSPACE**($f(n)$) is closed under complement.

I know that most likely my answer is wrong. Can someone explain why?

# Answer
Your reasoning is essentially **correct**. Assuming your TMs are deciders (i.e., they must also properly reject their inputs), you don't even need an extra step in your algorithm; you can just swap the accept and reject states of your TM (just like you do with DFAs!).

In case your TMs are only defined as acceptors (i.e., a word not in the language will not necessarily be explicitly rejected, just not accepted), things are a bit more complex. In fact, we must then require more of $f$, namely that it is space-constructible; that is, given $n$ (unary encoded), we should be able to compute $f(n)$ (binary encoded) in space not greater than the value $f(n)$ itself. This property holds for practically all "standard" functions you know.

If that is the case, then, given a TM $A$ which accepts a language in space bounded by $f$, we proceed as follows:

1. Compute $f(n)$ (using $f(n)$ space).
2. Initialize a counter with the value $f(n)$. This counter need not use more space than what was already used in step 1; for example, we store it in a separate track of the TM tape.
3. Simulate $A$. For every step $A$ takes, decrement the counter. If the counter reaches zero, then enter the reject state (or loop without ever accepting).

This takes at most $f(n)$ space in steps 1 and 3 (and we reuse the tape in step 3), while step 2 does not take any additional space at all since representing the counter uses space on the order of $\log f(n)$, which is smaller than $f(n)$ (which is necessarily an integer), and we use a separate track for it.
> 0 votes

# Answer
> Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement,\[8\] because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases.

source
> -3 votes

---
Tags: complexity-theory, complexity-classes, closure-properties
---


# Question
Title: Categorising problems into complexity classes
Am I correct in saying that there are two ways to categorise a problem in complexity theory:

* Find an algorithm that solves it. If the algorithm runs in polynomial time, then we can put it into P-class. If not, then we can put it into EXP.
* Provide a reduction that this problem is no hard than another problem, to which we know the complexity class for.

If I cannot find a reduction and I do not have an algorithm, what is the "default" complexity class? I'm guessing it would be in the class of problems which cannot be solved until we find an algorithm.

# Answer
Your reasoning seems correct, but you are missing a crucial step once the second bullet point is done with: You check that your problem is also complete for the class $C$ you have found for it. For instance, if you have a problem $P$ and show it is reducible to a complete problem in $\mathsf{PP}$, then you are not done yet. For all we know, $P$ could be $\mathsf{PP}$-complete, but it could also be in $\mathsf{NP}$, or $\mathsf{BPP}$, etc. Therefore, to finish classifying $P$, you should be able to find a class it is complete for—if possible; after all, there are classes which are not closed under (poly-time many-one) reductions—, or provide some good evidence why it could not be in a class which is known (or conjectured) to be strictly below $C$.

> If I cannot find a reduction and I do not have an algorithm, what is the "default" complexity class?

Assuming your problem is decidable, the "default" complexity class is $\mathsf{R}$, the class of recursive languages. Improving on this is only possible by producing an algorithm whose time complexity you can prove or, alternatively, proving a reduction to some other problem for which this is the case; that is, essentially what you wrote in your question. There is no such thing as a "class of problems which cannot be solved until we find an algorithm" in complexity theory; that would be the domain of *computability* theory (i.e., problems which are not known to be decidable).
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Why sum of two binary numbers cannot be determined in $NC^0$ but in $AC^0$?
Why sum of two binary numbers cannot be determined in $NC^0$ but it can be determined in $AC^0$?

# Answer
an $NC^0$ can only consider circuits of fan-in 2. If we try to adding with a Full-Adder with Lookahead Gatter to calculate the carry, needs every Full-Adder 3 Input signals. But in $NC^0$ are only 2 inputs allowed. If we try to replace Full-Adder with other logic gatters, we hurt the depth of the circuit.

image-source: https://upload.wikimedia.org/wikipedia/commons/thumb/0/04/4-bit\_carry\_lookahead\_adder.svg/1000px-4-bit\_carry\_lookahead\_adder.svg.png
> 1 votes

# Answer
In an $\mathsf{NC^0}$ circuit, every output bit depends on a bounded number of input bits. But the $k$th bit of the output (counting from the LSB) depends on the first $k$th bits of each input.

To see that $\mathsf{AC^0}$ circuits can compute addition, we need to produce such a circuit. Hopefully you have seen such circuits, and otherwise perhaps you can construct them on your own. Give it a shot.
> 2 votes

---
Tags: complexity-theory, circuits, nc
---


title: Absorption Law Proof by Algebra

text:
# Question
Title: Absorption Law Proof by Algebra
I'm struggling to understand the absorption law proof and I hope maybe you could help me out.

The absorption law states that: $X + XY = X$
Which is equivalent to $(X \cdot 1) + (XY) = X$

No problem yet, it's this next step that stumps me. How can I apply the distributive law when there are two "brackets"?

**How can I manipulate $(X \cdot 1) + (XY) = X$ to give me $X \cdot (1+Y)$?**

I understand that the absorption law works. I would just like to see how the algebra proof works.

Thank you!

# Answer
> 10 votes
First of all, this is a math question.

I think you are confused on how brackets are used. They indicate *precedence* of operations, and can be used *anywhere*, even in places where such indication is not necessary. For example, $$3 \times 5 + 8$$ and $$(3 \times 5) + 8$$ are both legitimate expressions and they mean *exactly the same thing*.

Your expression $$(x \cdot 1) + (x \cdot y)$$ is exactly the same as $$x \cdot 1 + x \cdot y.$$ So we may calculate $$(x \cdot 1) + (x \cdot y) = x \cdot (1 + y) = x \cdot 1 = x.$$

# Answer
> 2 votes
Apply the distributive law on $x\land(1\lor y)$ and see what you get.

# Answer
> 0 votes
Try and think about it the other way. Can you legally go from the step below to the step above? If yes then it is fine( at least in this case) to go from top to bottom too.

---
Tags: boolean-algebra
---


# Question
Title: Upper bound $T(n) = 9T(\sqrt[3]{n}) + O(1)$
The problem is this: Use the recursion-tree method to give a good asymptotic upper bound on $$ T(n) = 9T(\sqrt\[3\]n) + \Theta(1). $$ I am able to get the tree started and find a pattern with the sub-problems, but I am having difficulty finding the total cost of the running times throughout the tree. I cannot figure out how to get the number of sub-problems at depth $i$ when $n=1$. I have a feeling the answer is $O(\log\_3 n)$, but I cannot verify that at the moment. Any help would be appreciated.

The recurrence can be written as $$T(n) = 9T(\sqrt\[3\]n) + C, $$ where $C$ is some constant, since any constant will always be treated as 1 asymptotically. My recursion tree is explained by each level below:

Level 0: This is the constant $C$

Level 1: $T(\sqrt\[3\]n)$ is written 9 times which represent the sub-problems of $C$. This adds up to $9C\sqrt\[3\]n$.

Level 2: Each of the 9 sub-problems from level 1 gets divided into 9 more sub-problems, which are each written as $T(\sqrt\[9\]n)$. All of these add up to $81C\sqrt\[9\]n$.

Sub-Problem Sizes and Nodes: The number of nodes at depth $i$ is $9^i$. We know that the sub-problem size for a node at depth $i$ is $n^{1/3^i}$. The problem size hits $n=1$ when this size equals 1. Solving for $i$ yields:

$$ (n^{1/3^i})^{3i} = 1^{3i} n = 1^{3i}. $$

This results in $n$ being 1 which doesn't give a logarithmic form!

# Answer
> 2 votes
You can solve this using the master theorem, whose proof uses a recursion tree argument.

Define $S(n) = T(2^n)$. The main observation is that $\sqrt\[3\]{2^n} = 2^{n/3}$, and so $$ S(n) = 9S(n/3) + O(1). $$ The solution is $S(n) = \Theta(n^2)$, and so $$ T(n) = S(\log n) = \Theta(\log^2 n).$$

You can also open the recurrence directly, obtaining $$ T(n) \propto 1 + 9n^{1/3} + 9^2 n^{1/3^2} + 9^3 n^{1/3^3} + \cdots. $$ The general term is $9^i n^{1/3^i}$. The recurrence will terminate when $n^{1/3^i} \approx 1$, which happens when $3^i \approx \log n$, that is, when $i \approx \log\_3 \log n$. For this value of $i$, $$ 9^i = 3^{2\log\_3 \log n} = \log^2 n. $$ This is the value of the bottom level of the tree. The contribution of the other levels is negligible in comparison, which is something you have to prove by calculation.

---
Tags: recurrence-relation
---


title: Church Turing thesis

text:
# Question
Title: Church Turing thesis
What is the exact statement of the Church Turing thesis?

Is it fair to say anything computable in the physical world can be computed by a Turing machine? If so, how does a Turing machine handle continuous variable computations (for example, computing solutions to differential equations or storing/computing any real number)? It will take infinitely many tape squares to specify anything continuous. If the input itself is infinite, what does it even mean to compute based on the infinite input?

# Answer
Neither physical computers nor the Turing machine model can *exactly* represent the value of a continuous quantity or a ~~non-rational~~ transcendental real number. They can, for example, only approximate $\pi$ by calculating or storing its value to some finite (but maybe very large) number of decimal places.

You are right - any computation that requires an "infinitely long" input (e.g. "given an infinite list of integers, output the largest integer in the list") will take an infinite number of steps to finish (or even just to read its input), which is the same as saying it will never finish. But part of the definition of an algorithm is that it can be completed in a finite number of steps. So a computation on an infinite input cannot be expressed as an algorithm, and so it falls outside of the boundaries of the Church-Turing thesis.
> 2 votes

---
Tags: computability
---


# Question
Title: Search vs planning in artificial intelligence
I'm studying artificial intelligence following the Russell & Norvig book. We did a search and planning part that for me is the same (at least on the representation). I'd like to know what is the difference between these two techniques, but I couldn't find it.

Looking online I found this resource: Planning and Search, where it says: "The main difference between search and planning is the representation of states."

Is the difference between these two techniques limited to the representation?

# Answer
Short answer is "Yes".

Long answer is "No":

As far as I am concerned the difference is limited to a specific author/lecture: (to the best of my understanding of the slides) The author of the linked slides does not want to refer to "search" as a technique like planning, but rather as a general procedure.

Planning is the process of finding a set of (valid) actions that transform an initial state (set of properties) to a goal state. Such a problem can be represented by a state space graph, where each node defines a complete world state (i.e. a set of properties). Two nodes are connected if there exists a valid action transforming one state into another.

* "Search" is the general procedure of finding a solution by searching the problem space. In this case it is the process of iterating a state space graph starting at the initial node, trying to find a path to the goal node, i.e., using DFS. The search problem is given an (perhaps implicit) representation of the graph and is not concerned about internal properties of nodes.
* A non-search "Planning" algorithm on the other side may make use of the logical properties of the states to iterate the state space graph.

However, I would like to note that most "Planning" algorithms do use some kind of search procedure on the state space graph, significantly improving the search using planning-heuristics: Consider the graph given on slide 4 (of the referenced link). The complete graph represents the planning problem. The search "only sees" nodes and edges. A DFS would simply iterate all possible paths until a solution is found. A heuristic (planning algorithm) may use additional relations between properties (i.e. getting milk implies going to the supermarket first).

---

Informal definition of plan: the solution to a planning problem. A sequence of actions that translate the initial (world) state into the goal state.

In terms of the (graph) search this would be a list of edges to traverse. If there exists a valid plan, then there exists a path in the graph.

---

(this may be a little out of scope) Since planning is in general PSPACE-complete naive search algorithms perform exceptionally bad on many instances. Common heuristics/techniques used in planning are based on the relaxation of the state space graph, i.e., by relaxing preconditions or effects (resulting in easier problems; in P, or NP) which can be solved "easily". If you are interested in planning that is somewhat separated from "search" you might wan to take a look at hierarchical task networks (HTN) which is basically planning with additional domain knowledge.
> 2 votes

---
Tags: machine-learning, artificial-intelligence, search, planning
---


title: Forcing an edge to be in S-T min-cut

text:
# Question
Title: Forcing an edge to be in S-T min-cut
Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e.

So, I tried couple of steps, first, I know I must saturate $e$ so it could be in any min-cut. I tried to add a supersource that connects to $u$ (with infinite capacity) and a supersink that connects to $v$. But that will only saturate $e$ if it is not yet been saturated, not force it to be in a min cut $s,t$. I also thought maybe to reduce an epsilon from the capacity of $e$, but I am not sure if it is enough.

I also tried to connect the supersource to all of u neighbors and the supersink to all of v neighbors and then reduce an epsilon from e. Again I don’t know if that’s enough.

I’m not sure how to continue (or if i can) from here or if I’m missing something.

# Answer
> 1 votes
Remove $u$ and $v$ (as well as all edges connected to them), and for any removed edge $(u,x)$, add an edge from $s$ to $x$ with the same capacity; for any removed edge $(y,v)$, add an edge from $y$ to $t$ with the same capacity. Now find a min cut in this new graph. The partition of nodes in this cut suggests a min cut among those including $e$ in the original graph.

---
Tags: algorithms, graphs, network-flow, minimum-cuts
---


# Question
Title: What is the "spatial information" in convolutional neural network
deep learning research papers always claim that deeper layers of CNN have good "semantic information" but poor "spatial information". What is the spatial information exactly. Is that some activations in deeper layers?

# Answer
> 4 votes
Spatial Information refers to information having location-based relation with other information.

For example,
00**1**00
0**11**00
00**1**00
00**1**00

This looks like the number "1".

If this was represented in a single line,
00**11**000**111**0000**11**0000**11**00

It wouldn't be recognizable.

Earlier layers of CNN are convolutional layers, which take into account the image as a 2D (spatial) information. Whereas, the deeper layers flatten that (convoluted) information.

# Answer
> 4 votes
I think the authors are referring to **spatial invariance**. I will explain it on image classification/recognition example.

Convolutional Neural Networks are designed to be spatially invariant, that is - they are not sensitive to the position of, for example, object in the picture. The deeper you go into layers, the originally not so (pixelwise) similar objects (or usually parts of objects) are becoming more similar (and this is achieved via convolution). At the deepest layers we have extracted features with no information on where they were positioned on the original image. We even lose the information on pixel-size of original objects because of another process in CNN called pooling.

Convolution is the key for why CNNs perform better than any other model in such "human-like" tasks like recognizing specific objects in the picture, words in a recorded speech,$\ldots$.

**Further "reading":**
$\ $ - Convolution is nicely explained and visualized in this YouTube video.
$\ $ - A more lengthy and deeper video on this subject is Convolutional Neural Networks - The Math of Intelligence

# Answer
> 2 votes
Spatial refers to space.

So, what is space in images?

Space represents the 2D plane(x-y) in images. Coming back to the question, 'What is spatial information in cnn?', for example in first conv layer, it extracts spatial information like egdes, corners etc. and in other conv layer it extracts spatial information like eyes, nose etc.

This is spatial information in images. CNN's don't maintain spatial relationship among features. Advanced capsnet addresses this problem.

---
Tags: machine-learning
---


# Question
Title: Is there a problem in this BN form language?
I am working on a simple text query language. I am using the SLY parser, which itself is an LR parser/shift-reduce parser. I am running into problems with the following language specification, but I don't understand why. All I'm trying to do is appropriately group logical statements involving the operators AND and OR (in which AND gets precedence over OR and the statements are left associative) and "words", which is basically anything other than "AND" or "OR". The language is below. What is the problem?

```
LOGICAL ::= <WORD> <OPERATOR> <WORD>
        | <WORD> <OPERATOR> <LOGICAL>
        | <LOGICAL> <OPERATOR> <WORD>
        | <LOGICAL> <OPERATOR> <WORD>

OPERATOR ::= "AND"
            | "OR"

WORD ::= any string other than "AND" or "OR"

```

Also, for the record I don't know how to express "WORD" in a more formal way, so I'd appreciate any input.

# Answer
That grammar has two problems.

1. It's ambiguous. You say that you want to give `AND` precedence over `OR` and make both operators left-associative, but your grammar does not reflect that goal since it does not distinguish `AND` from `OR` and it explicitly accepts both left- and right-associative parses:

```
<WORD> <OPERATOR> <LOGICAL>    (* right associative *)
<LOGICAL> <OPERATOR> <WORD>    (* left associative *)

```
2. On a more minor level, probably a typo, your third and fourth productions are identical.

It's possible that you have tried to fix the issue by using precedence declarations in your parser generator tool. Precedence declarations are not part of BNF, and incorrect precedence declarations are really a programming error, rather than an issue in parser theory.

If you have such a problem, you should probably ask a question on a programming site, such as StackOverflow, and comply with the usual rules of including a complete reproducible example. However, in the usual approach to using precedence to resolve parser ambiguity, it is important that you don't have explicit parser ambiguity, as above. Thus, a "traditional" precedence-augmented BNF grammar (as per the Dragon book) would look like this:

```
%left <OR>
%left <AND>

<LOGICAL> ::= <WORD>
          |   <LOGICAL> <OR> <LOGICAL>
          |   <LOGICAL> <AND> <LOGICAL>

```
> 1 votes

---
Tags: formal-languages
---