# Question
Title: Conditions to apply Source Coding Theorem
I was wondering what are the conditions to apply source coding theorem (SCT).

**1. Is it applied only to uniform-length coding, what about variable-length coding, does it also satisfy SCT?**

I was asking because in my lecture, SCT is only discussed in uniform coding section.

**2. Is the result of SCT for uniquely decodable coding or is it for lossless coding?**

In Wikipedia SCT, it's said $f$ is unique decodable code, then we have SCT. In my lecture, it gives me an impression that SCT is generally applied to all lossless coding.

# Answer
> 2 votes
1. It is an average in bits/symbol and does apply to all coding schemes.
2. You're correct, the number of bits/symbol needed is equal or larger than the entropy rate (asymptotically, though) of the source for any lossless code.
3. If you allow for lossy coding, then a generalization called rate-distortion function is needed to lower bound the rate required.

# Answer
> 2 votes
The source coding theorem is a statement about uniform-length coding. It tells you how long the uniform length should be in order to guarantee high success probability. It can be *proved* using variable-length coding, but the statement itself just doesn't concern variable-length coding. It is meaningless to ask whether variable-length coding "satisfies" the source coding theorem.

In more detail, suppose there is a source with entropy $H$. We want to encode $n$ i.i.d. samples of the source using as few bits as possible. Generally speaking, if you want to guarantee that the encoding always be decodable back to the original samples, then you cannot bound the length of the encoding (see the example below). Instead, we are content with a guarantee that the decoding will be successful with probability tending to 1. The source coding theorem states that such an encoding is possible using $nR$ bits if and only if $R\>H$.

To see why error is necessary, consider a source which is distributed geometrically $G(1/2)$, that is, with probability $1/2$ it equals $1$, with probability $1/4$ it equals $2$, with probability $1/8$ it equals $3$, and so on. The entropy of this source is finite (in fact, 2 bits), but since there are infinitely many potential outcome, if we want to guarantee that decoding will be successful, we must allow a message of unbounded length.

One way to prove the *if* part of the theorem is using variable-length encoding. It is known that $m$ samples can be encoded as a prefix code using at most $mH+1$ bits in expectation. Taking $m = \sqrt{n}$, this shows that $n$ samples can be encoded using a variable-length encoding of length at most $nH + \sqrt{n}$ bits in expectation. If $R \> H$ then for large $n$, $nH + \sqrt{n}$ will be much smaller than $nR$, and furthermore, it can be shown (using the law of large numbers) that it is highly likely that this variable-length encoding will use at most $nR$ bits. Therefore we can take as our uniform-length encoding the first $nR$ bits of this variable-length encoding (padding it arbitrarily if needed).

The *only if* part of the theorem does have a counterpart for variable-length codes: any prefix code for a source with entropy $H$ must have expected length at least $H$. This is a nice exercise.

---

As for your second question, lossless encoding is an encoding scheme which can be decoded exactly. This is in contrast to JPEG, for example, which is a lossy encoding – given an image, if you compress it to JPEG and then decompress it, you get a slightly different image.

In contrast, uniquely decodable encoding is a term used to describe variable-length codes with the property that the concatenation of several codewords can be segmented uniquely into codewords. Every uniform-length code is automatically uniquely decodable.

The two terms describe different aspects of the encoding. The first term states that the encoding aims to reconstruct the source exactly rather than approximately. The second term states that the encoding can be used to encode a sequence rather than just a single item.

---
Tags: information-theory, coding-theory
---


# Question
Title: Printing all paths of a tree and sorting the weight of edges
Let $T=(V,E)$ be tree and each edge has a positive scalar weight. I need to print all paths in the tree and then sort the weight of edges in each paths. it needs $O(n^3\log(n))$ time. To solve this problem we can rooted the tree in a leaf and print all vertices by preorder algorithm and in each step we insert the new edge weight. After meeting all vertices we can delete the root and consider another leaf as the root. The complexity seems $O(n^2\log(n)).$ Can we reduce the complexity, for example, $O(n^2)$?

# Answer
> 1 votes
You can't do better than $\Omega(n^3)$ running time.

In a tree, there is a path between every pair of vertices, so there are $\Theta(n^2)$ paths. The average path length can be $\Theta(n)$. So the total length of the output can be $\Theta(n^3)$. Obviously, no algorithm can run faster than that, since it takes at least $\Theta(n^3)$ time just to write out the output.

---
Tags: algorithms, complexity-theory, graphs, graph-traversal
---


title: How to prove a reduction

text:
# Question
Title: How to prove a reduction
I'm just a little confused about the wordings for reductions and would appreciate some help as I am very new to reductions.

I have a question where I have two sets, A and B, and I have to provide a reduction A $\leq\_p$ B and then I have to prove that the reduction is correct.

What does this mean exactly?

For the reduction portion do I have to:

1. Provide some sort of explanation of B in terms of A?
2. Provide some sort of explanation of A in terms of B?
3. Both 1 & 2?

And then I'm assuming to prove the reduction is correct, I need to show A $\implies$ B as well as B $\implies$ A?

(The exact question has A as the set of un-directed graphs with a Hamiltonian path and B is the set of un-directed graphs with a Hamiltonian cycle)

Any clarification would be greatly appreciated!!

Thanks.

# Answer
> 1 votes
Follow the definition of $\leq\_p$.

You have to find a function $f$ (define it!), computable in polynomial time (prove this!) such that

$$ \begin{array}{l} \forall x.\ x\in A \implies f(x)\in B \\ \forall x.\ x\notin A \implies f(x)\notin B \end{array} $$ (two more proofs!)

More intuitively, $f$ converts instances of $A$ (i.e. $x$) into instances for $B$ ($f(x)$), and must map $A$ inside $B$, and the complement of $A$ inside the complement of $B$. Very, very roughly, it describes how to solve $A$ exploiting $B$.

Finally, never write nonsense formulas like $A \implies B$ since sets do not imply other sets. Try to be as formal as you can, at least when you have not yet mastered the definition.

---
Tags: time-complexity, reductions
---


# Question
Title: What's the correct term for this analog of cryptography?
Suppose there is a communications channel between two parties. Suppose I want to send information through this channel, but I want to make it look like noise. Ie, I don't necessarily want to encrypt it, though I'm not prohibiting encryption - the point is I want to be able to transmit information to someone else such that what is sent across the channel cannot be distinguished from random noise by any potential eavesdropper.

Maybe something like the above is impossible to do "perfectly", but in any case the question I'm asking is - what is the correct term/keywords for problems in the spirit of what I described above?

Is there a mathematical theory of something of this type?

# Answer
It's not an exact match to your question, but you're probably looking for something in the field of steganography.
> 2 votes

# Answer
As @mhum suggests, looking at techniques from the field of steganography is probably an excellent starting point... but you might also be interested in subliminal channels.
> 0 votes

---
Tags: cryptography
---


title: Comparing Algorithm Strategies

text:
# Question
Title: Comparing Algorithm Strategies
Are **Brute Force Algorithm** and **Exhaustive Search** both references to the same ideas?

# Answer
> 2 votes
Yes. Both refer to the idea of basically trying every possible combination to check whether the desired output is met. One is called exhaustive search because we search over every possible combination till combinations are "exhausted". Brute force is basically the same idea by trying every combination as well without any optimizations or clever algorithms. We are basically using the force the computer to solve a problem.

---
Tags: algorithms, algorithm-analysis, data-structures
---


# Question
Title: How to solve a polynomial of the form y = ax^3 + bx^2 + cx + d using the incremental algorithm in computer graphics
I am studying Computer Graphics and need to design an incremental algorithm for solving the polynomial $y = ax^3 + bx^2 + cx + d$, and then implement that in OpenGL. The input will be the values of $a, b,c,d$ and the desired output is a *line/curve* to be drawn. The values of $x$ would be in the range $1\leq x\leq100$. The algorithm needs to be very efficient hence I am required to use only *addition* operation, as multiplication is less efficient.

It would be similar to this technique, but here the polynomial to be considered is the one given above. I have searched a lot on the Internet but cannot find the required solution, because most of the examples solve the equation $y = mx+b$.

Can anyone kindly guide me how to solve it or which method should be applied to solve it?

# Answer
You have f(x). Let g(x) = f(x+1) - f(x). Let h(x) = g(x+1) - g(x). Let k(x) = h(x+1) - h(x). It turns out that k(x) is a constant.

Calculate f(x), g(x), h(x) and k(x) for x = 1. Then you calculate f(x+1) = f(x) + g(x), g(x+1) = g(x) + h(x), h(x+1) = h(x) + k(x), and k(x) is a constant.
> 3 votes

---
Tags: algorithms, graphics, polynomials
---


# Question
Title: Is undecidable(complement of R) a subset of NP-hard?
Is there an undecidable problem which is not NP-hard?

# Answer
> 6 votes
If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$\neq$NP. If $A$ is a set and $f\_i$ reduces SAT to $A$ in polytime, then $f\_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f\_i$ to get a polytime algorithm for SAT.

We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f\_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f\_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.

The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f\_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f\_i$ is infinite). We define $A$ on $f\_i(s)$ so that $s \in SAT$ iff $f\_i(s) \notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s \in A$ iff $|s| \in K$.

By construction, no polytime $f\_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n \in K$ (for $n \geq 2$) by taking a majority of three strings of length $n$.

# Answer
> 2 votes
One example of an undecidable language that is not NP-hard, unless P = NP, is $$ L = \\{ 1^n : n \text{ is the natural number for a TM which halts on input } \epsilon\\}. $$ I have explained this answer through a more general theorem in this answer on mathSE.

---
Tags: complexity-theory, undecidability
---


# Question
Title: Convert (x + y = z) to propositional logic formula for 8-bit numbers
(Note: this was asked in the cstheory stackexchange, but I was told this is a more appropriate place for it.)

I have three 8-bit 2's-complement numbers (X, Y, and Z). I want to find a propositional logic formula using only the variables (x1, x2... x8, y1... y8, z1... z8), where xi is the ith bit of x which expresses the concept that X + Y = Z. How would I go about doing this?

# Answer
You can obtain a formula in CNF form by writing down a truth table (with $2^{24}$ rows) and then converting each row to a single clause. This will yield a formula with $2^{24}$ clauses, but the method is straightforward.

If you want a shorter formula, I suggest using logic synthesis, e.g., Quine-McClusky, Espresso.

The usual path to get a small formula is to allow introduction of additional variables, build a circuit (e.g., an adder circuit followed by a comparator), then convert to a formula using the Tseitin transform. This yields much smaller formulas, but it requires introducing extra variables, which you said you don't want.
> 1 votes

---
Tags: propositional-logic, bit-manipulation, bit-blasting
---


# Question
Title: How do you find the inverse of an arbitrary $f(x)$ if $f$ isn't one-way?
I'm considering the following definition of one-way functions:

> Let $f : \\{0,1\\}^k \rightarrow \\{0,1\\}^k$ and $b : \\{0,1\\}^k \rightarrow \\{0,1\\}$ be computable in poly($k$) time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all polynomial-time randomized algorithms $A$ and all constants $c$, $$\underset{x\in\\{0,1\\}^k}{\mathbb{E}}\Big\[\mathbb{P}\[A(f(x))=b(x)\]\Big\]=\frac{1}{2}+o(k^{-c})$$

Note that $A(f(x))=b(x)$ is an event, not because $x$ is random but because $A$ is a randomized algorithm.
Now suppose $f$ *isn't* a one-way function, then this expectation will be noticeably different from $1/2$. But for any particular $x$ the probability might still be close to $1/2$. Indeed the probability could be exactly $1/2$ (or even 0) for a large fraction of the $x$, provided for the remaining $x$ $f(x)$ can be inverted with sufficient accuracy to make the expectation noticeably different from $1/2$ again.
So what do I do if I'm presented with such an $f(x)$? The fact that many other $f(x)$ can easily be inverted seems of little consolation then. I don't see any way to invert $f$ then. In particular in connection with pseudorandom number generators I'm reading statements like

> We will show that if any tester $A$ can tell the difference between $g(x) = (f(x),\\,b(x))$ and a random string, then we can use $A$ to "break" our one-way function, and calculate $b(x)$ from $f(x)$ with $1/\text{poly}(k)$ probability.

I can read this in two different ways.

1. $x$ is random and there's a $1/\text{poly}(k)$ chance of getting an $x$ for which $b(x)$ can be computed from $f(x)$ exactly.
2. For every $x$ $b(x)$ can be computed from $f(x)$ with a $1/\text{poly}(k)$ chance of success.

(1) has the problem that the text presents a randomized algorithm to compute $b(x)$ from $f(x).$ It *isn't* exact.
(2) is false based on the preceding discussion.

# Answer
> 1 votes
Both (1) and (2) are possible. (It's also possible to have a combination of them.) It doesn't really matter which holds; either way, that means that $f$ is not one-way.

You say (2) is false because of the preceding discussion, but I'm not exactly sure why you think it is false. One-wayness is not a property of a specific value of $x$; rather, it is a property of a function $f$. And, just because a function $f$ is not one-way doesn't mean it can be inverted for every possible output. If $f$ can be inverted on a significant fraction of outputs, it is not one-way. If $f$ can be inverted on all outputs, with a significant probability, it is not one-way.

Perhaps the confusion comes from a misunderstanding about what the definition of a one-way function is. The definition you quote at the beginning is not the definition of a one-way function. Rather, it's the definition of a hardcore bit.

The part you quoted appears to claim/imply that it is the definition of a one-way function with hardcore bit (which is not the same as the definition of a one-way function). That claim/implication is not correct. The precise statement is that this is the definition of a function with hardcore bit. This definition implies nothing about onewayness. So why did they call it the definition of a one-way function with hardcore bit? I don't know; you'd have to ask the author. But my guess is that this definition is normally only used with functions you already know to be one-way, so there's an implicit assumption that $f$ is already known to be one-way, and given such an $f$, the definition is describing what it means for $b$ to be hardcore for $f$.

You say "suppose $f$ isn't one-way, then this expectation will be noticeably different from 1/2". That actually doesn't follow. You can have a function $f$ that isn't one-way but *does* have a hardcore bit. Then the expectation will *not* be noticeably different from 1/2. E.g., consider the function $f$ given by $f(x)=0$: it's not one-way, but it does have a hardcore bit, and the expectation is exactly 1/2.

It sounds like you want to understand one-wayness. If so, hardcore bits are a distraction. You should be looking for the definition of a one-way function and trying to understand that, not looking at the definition of a hardcore bit.

---
Tags: randomized-algorithms, pseudo-random-generators, one-way-functions
---


# Question
Title: Find the center node on a weighted, non-directed graph
So I have a problem, and it's an assignment from school.
This is a figure made out of matchsticks. The goal is to find the optimal location to light up the figure so that it burns in minimal time. You can only light it up at integer positions (C,B) but not A. Different matchsticks may have different burn times.

## My approach to this problem:

* Iterate through every possible "light up" point
* For every "light up" point, light up the figure and wait it to burn completely
* Store the time it took to burn
* Once iteration is complete, find the lowest time and there's your answer

---

## The problems with my approach

* Burning each figure will take a while since it's done realtime. It's also possible to do it faster then realtime, but I still don't think it's a viable solution.

---

## Problems with center of a weighted graph:

* What if we come up with A as the center?

## Solution:

* Just pick the next potential center and check if it's a valid "light up" point.

---

So I'm looking for a graph algorithm that can calculate the center on a weighted graph. I've never dealt with graph algorithms before, so that's why I'm asking here. I'm also just asking for you to point me in the right direction, and not write the code for me (although I guess some pseudo code will come in handy).

# Answer
> 1 votes
Use the Floyd-Warshall algorithm to compute all-pairs shortest paths (i.e., compute the distance between each pair of nodes). Then it is easy to find the center of the graph by enumerating all possibilities for the center node. The running time will be $O(n^3)$.

---
Tags: graphs, weighted-graphs
---


# Question
Title: Does every language in BPP have a mapping reduction to ATM?
Does every language $C$ in the class $BPP$ have a mapping reduction to $A\_{TM}$? $(C\leq \_{m} A\_{TM})$

$BPP$ is the class of languages that have a probabilistic $TM$ that accepts them with an error $\epsilon$ less than 1/3.

$A\_{TM}$ is the acceptance language, takes as input a $TM$ description of $M$ and a word w, then determines if w is in $M$'s langugae. $A\_{TM}$ is of course undecidable!

# Answer
> 2 votes
Yes.

Every decidable language reduces to $A\_{\mathrm{TM}}$.

Every language in **BPP** is decidable because the definition requires that every execution of the probabilistic machine halts in polynomial time. So you can just simulate out all the possibilities and compute the probability that the machine accepts.

---
Tags: complexity-theory, probabilistic-algorithms
---


title: Advantages of FPGAs over GPUs

text:
# Question
Title: Advantages of FPGAs over GPUs
What are the advantages of using FPGAs over GPGPUs? It seems like GPGPUs have the best of CPUs and GPUs combined.

# Answer
There are specific applications for which GPUs are useful. For example, they are useful when we want to perform same operation(use same instructions) but for many different data elements in parallel. For example, add 1K elements in parallel. Such workloads are said to have Data Parallelism.

This is not the case with FPGAs. They are highly customisable and can be made to do anything you want and not just highly data parallel operations. Hence, FPGAs offers much more freedom for designers than GPUs.
> 4 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Is there a standard way to define a formal language transformer?
I'm about to study a system that takes words in a formal language $L$ and converts them into words in a different formal language $L'$. In other words: a *formal language transformer*. I was wondering if there is **literature on formal language transformers, some standard way of studying, and defining them**?

All I found are a 1995 paper by Cousot & Cousot on program analysis where formal language transformers are mentioned, but not really studied, and a 2005 presentation by Jaeho Shin that mentions the Cousot & Cousot paper. But maybe I'm looking in the wrong place or maybe I'm using the wrong vocabulary?

After all the effort in defining and studying the very many kinds of formal languages, it seems strange to me that nobody has bothered studying their transformations into each other.

# Answer
> 3 votes
Without knowing what kind of transformation you compute, it's unlikely that there's a useful word. Assuming that any two inputs are processed independently of each other, you're looking at (computable) function(al)s from $A^\* \to B^\*$ with two alphabets $A$ and $B$.

Here are some specific kinds of transformations:

---
Tags: formal-languages
---


# Question
Title: How to compute quotient subgroup efficiently?
Let $G$ be a finite group given by the table representation and a normal subgroup $H$ of $G$ is given. I want to compute $G/H$ that is quotient group.

Model of computation is RAM

For all pair of $a$ and $b$ in $G$ just check $a.b - b.a = 0$ , but it is going to take much time $O(n^2)$. Is there a faster algorithm to solve this problem?

# Answer
Based on the following snippet from https://en.wikipedia.org/wiki/Quotient\_group:

> In a quotient of a group, the equivalence class of the identity element is always a normal subgroup of the original group, and the other equivalence classes are precisely the cosets of that normal subgroup.

It seems that you can simply set $H$ to be the identity element of $G/H$ (taking O(1) time), and then for each element $g \in G$ *that has not yet been assigned to any coset*, calculate the (say, left) coset of $H$ w.r.t. $g$ explicitly: $\\{gh : h \in H\\}$, and assign all such elements $gh$ (*not* just the $g$ we started with) to this coset. Calculating the coset for a particular $g$ takes $O(|H|)$ time, but the entire second phase takes only $O(n)$ time overall, since we only consider elements $g \in G$ that have not yet been assigned to a coset -- this is allowed because (according to that page) the cosets form an equivalence class, meaning no element can appear in two different cosets.
> 0 votes

---
Tags: algorithms, computer-algebra, group-theory
---


# Question
Title: what does the author mean by directory structure in operating system?
I'm reading *Operating System Concepts* by Avi Silberschatz(9thE), in section 11.4 File-System Mounting, the author explains the steps of filesystem mounting as follows:

> 1. The operating system is given the name of the device and the mount point—the location within the file structure where the file system is to be attached.
> 2. Next, the operating system verifies that the device contains a valid file system.
> 3. Finally, **the operating system notes in its directory structure** that a file system is mounted at the specified mount point.

I'm confused with the final step, since to the best of my knowledge, the directory structure is stored somewhere on the disk, which records the files' information -- such as name, location, size, and type. Then what does the author mean by **directory structure in operating system**? Is it the same directory on disk?

Additionally, which part finishes the conversion from file name to physical address on disk? Is it the disk driver or the disk controller or done by processor with memory?

# Answer
> 1 votes
Step 3 of that description is indeed a bit confusing, and your comments are right. The short answer is that the OS keeps track, in memory, of the set of mounted file systems and where they are mounted.

---
Tags: operating-systems, filesystems
---


# Question
Title: Work-stealing: where and how many to steal
If one ignores the conflicts when accessing the dequeue in Work-Stealing algorithms, does it matter (and in what ways) if one steals from the top or bottom (or anywhere randomly) of the dequeue? Does it matter (and in what ways) if one steals one or more items ?

# Answer
I did some experiments about this myself a while back so I hope I can still give some insight. This approach is called "Idempotent Work Stealing" and was defined (to the best of my knowledge) here. It means that you can get items more than once but at least once. There are then three operations defined $put()$, $take()$, and $steal()$. The idea is that $put()$ and $take()$ are free of synchronisation only $take()$ uses atomics. When a thread has finished its queue (or stack) it uses $steal()$ on some other threads stack.
> 2 votes

---
Tags: algorithms, scheduling, threads
---


# Question
Title: Is finding cache size possible with information given?
An 8-way set-associative cache is used in a computer in which the real memory size is 222 bytes. The line size is 16 bytes, and there are 26 lines per set. A) What is the size of the cache in bytes?

What I (think) I understand: Cache line and cache block are synonymous. The textbook says that an n-way set-associative cache has n blocks(lines) per set. That conflicts with the next sentence that says "there are 26 lines per set." Is this problem incorrect or are my assumptions wrong?

# Answer
> 1 votes
An n-way set associative cache can store n different entries for a given index in the cache array. So the 8-way acts like an 8x multiplier as compared with a direct mapped cache (1-way set associative).

So, I would take it that the line size of 24 with 26 lines per set and 23-way set associative is 213 or 8k bytes.

A next question might be how big are the tags that are stored in the associations? 22 (from the address space) - 4 (for cache line size) - 6 (the number of entries in the array), means that a tag size of 12 bits is needed.

---
Tags: computer-architecture, cpu-cache, cpu, memory-hardware, cpu-pipelines
---


# Question
Title: How to calculate number of nodes opened by BFS?
In the below diagram, each node takes up a space of 2KB. I need to find the total memory consumed to reach the goal : I

I know that the equation for BFS is

b1 \+ b2 \+ ...... + (bd+1 \- b)

Where b is the branching factor and d the depth

But how do I calculate the branching factor in the below diagram, where the branches are **uneven**?

Also, is the depth on A node 0 or 1?

# Answer
> 0 votes
In the case of the above diagram, as you mention, there is no constant branching factor. This means that we cannot solve for the number of nodes explored using the formula you give above.

Instead, we must use knowledge of how BFS works in order to calculate which nodes were visited before **Node I** was found. In BFS, nodes adjacent to the current node are marked, and then placed in a queue. The next element in the queue is visited (and removed from the queue), and this process repeats. Use this process to figure out which nodes are visited before **Node I**, and then charge a cost of 2kB for visiting each node.

---
Tags: algorithms, algorithm-analysis, search-algorithms, search-trees
---


title: Runtime analysis of bit operations

text:
# Question
Title: Runtime analysis of bit operations
In class we have learned that division takes O($k^2$) where k is the bitlength of the numbers used in the operation. What would be the runtime of a function that looks like this?

```
while a % 2 == 0:
    a = a / 2

```

I am guessing the worst case is $O(log(k)k^2)$ as a decreases by 2 each time but each division takes $k^2$

# Answer
Numerical division of arbitrary numbers is $O(k^2)$, but division by 2 is a special case that is always $O(k)$, and `a % 2` is $O(1)$, since it only requires examining a single bit. Since the loop requires $O(k)$ iterations, that makes the whole computation $O(k^2)$ in terms of bit operations.

In practice, however, you'd either

* have `a` stored in a shift register to begin with, which means that the division (shift) operation is $O(1)$, making the overall implementation $O(k)$.
* use a pointer to find the first nonzero bit of `a` (which takes $O(k)$) and then copy the bits to the result just once (which is also $O(k)$), making the overall implementation $O(k)$
> 1 votes

# Answer
Take the case that $a=2^{63}$, so k = 63. The loop will iterate k times. Under the assumption that a division takes $O(k^2)$, the total is $O(k^3)$. On the other hand, that is not the worst case. The worst case is a = 0, where the algorithm never terminates.

Using clever methods, multiplication and division for the general case can actually be performed a bit slower than $O (k \log k)$, which would be relevant if k is say a few hundred thousand. But if a is a binary number, then division by 2 can be performed in O(k), so the algorithm (if you check for a = 0 first) takes $O (k^2)$.

On the other hand, assuming binary representation, you can do this a lot faster by counting the number of trailing zero bits in O (k), then shifting the number by that many bits in O (k), with a total of O (k).
> 0 votes

---
Tags: runtime-analysis
---


# Question
Title: If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP
If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP.

I am struggling with figuring this out. I know this means Y can be reduced to X, so if I could solve X I could solve Y. I can't solve X, but I have a certifier for X and complement(X). I am having trouble combining the reductions and certifiers to find a certifier for complement(Y).

# Answer
> 1 votes
Note that

$$ A \leq B \iff \overline{A} \leq \overline{B} $$

where $\overline{A}$ denotes the complement of $A$. Indeed, if $f$ is a reduction for either side, it is also a reduction for the other side (exercise: prove this using the definition of $\leq$).

From this, your statement quickly follows.

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


# Question
Title: Automatic softcore configuration based on intermediate representation (IR) compiler output
When compiling a piece of software (with LLVM for exmple), you first transform your code into some kind of intermediate representation (IR code). This IR code needs to be converted to your target specific assembly code.

When we have a fixed processor architecture, often optimizations are made to make the machine run a bit faster, or consume less memory. It is always a trade off when designing the ISA, is this computation general enough to dedicate a separate instruction for it, so that later on when compiling software, these optimizations can be made.

With soft cores, however, we could make a whole new processor every time we have a new piece of code. Often we see soft cores being designed for a specific purpose, while still keeping them general purpose enough so that they can be reused, or still work well when the software is changed.

It seems possible to, instead of first making designing the processor and then compiling the code for the target, making the processor based on your code. Profiling and debugging could be done on a general purpose machine running the intermediate representation code. Based on those results, an effective instruction set can be generated. With that instruction set, a soft core can be generated.

Designing an instruction set and building a good soft core and making a proper tool chain for target compilation steps is a lot of work, but it seems possible to automate this process. I could not find anything on this topic however.

Is this just too complex to do, and are we just better of having a few settings for your soft core with a bunch of optional extensions? Like you often see with soft cores like the Microblaze or NIOS II.

Or is this already a thing and can I just not find it? I do know of coarse grain reconfigurable architectures, but these are more for parallel computations and aim to replace FPGAs for some purposes.

Also, is this stack exchange the right place for these quite multidisciplinary questions?

# Answer
Soft cores are still intented to be able to run different applications and have a general purpose, with of course some new instructions or peripherals usefull for the needs of what will run on the FPGA.

When wanting to optimize only one application from a common software programming language to run on a FPGA, there are already some compilers trying to do this, like recently reconfigure.io which aims to use Go: https://reconfigure.io/

If the project doesn't need to be able to load and run new programs in a general way, you're better to not use a soft core as it will waste a lot of resources on your FPGA.

If for example you're using the LLVM IR representation of a software, you could effectively optimize a soft core for it, but it's losing the aim of a core to be able to run multiple programs efficiently. If you're intending to run only one program in an optimized way, generating an hardware description of it (like what you're doing by using languages such as VHDL or Verilog) will be more efficient.
> 1 votes

# Answer
An ISA is an interface specification between the hardware and the software. It's a "stake in the ground" that allows the software engineers (sequential thinkers) and the hardware engineers (parallel thinkers) to communicate and cooperate effectively when working on an application.

Removing that stake by making the ISA variable would require that everyone involved be equally expert in both domains.

A fixed ISA is not that much of an impediment to optimization anyway. Look at x86 — over the decades in which it has been in existence, there have been implementations that

* use multiple clocks to execute each instruction
* execute one instruction per clock
* execute multiple instructions per clock
> 1 votes

# Answer
This *is* possible, but the gains might not be as substantial as one would hope for, except in special cases.

A "soft core" is where you use a FPGA to build a processor. So, you are talking about taking a program, selecting a custom processor architecture, building that processor architecture on a FPGA, and then compiling the program to that custom architecture so it will run on the "soft core".

The problem with this approach is that soft cores are generally significantly slower than a dedicated processor, potentially by an order of magnitude or so (or even more). It's unlikely that the customization of the soft core can make up for that performance gap. In particular, if you choose a "soft core" that is basically doing the same thing as an existing dedicated processor, then it's likely that your soft core will be far slower than the dedicated processor. So you have to hope that your program is doing something so special, that you can identify a custom processor architecture that is so different from existing general-purpose processors, that you can regain more than a 10x speedup. While it might be possible in some narrow cases, that's usually hard, for most programs.

Alternatively, there's a more direct way to use a FPGA. Rather than using the FPGA to build a soft core, then compile your program to run on that soft core, you could compile the program to run directly on the FPGA. Or, you can try to identify the performance-critical inner loops of your program and compile them into logic for the FPGA. This is known as reconfigurable computing, and there is lots of research and commercial work on that problem. I suggest reading up on reconfigurable computing, where you'll find lots of information about it. It is in some sense a "better" version of what you are asking about.

One limitation of reconfigurable computing is that FPGAs are significantly slower than dedicated processors, as FPGAs are typically built with a slower and older process, so you have to identify some task in the program where custom hardware is significantly faster than a general microprocessor so that you can make up for this gap. Some programs have a core inner loop that *is* amenable to such speedups with custom hardware. However, many end-user programs don't have any obvious way to get big speedups like that. So, this ends up being something that only yields speedups for a subset of programs. Also, to be interesting, this approach also needs to be faster than the alternatives. Right now the GPGPU is a competitor: many of the programs that see speedups with custom hardware, also see speedups when run on a GPGPU, so the benefits of reconfigurable computing over using an existing GPGPU might not be large enough to warrant the cost and complexity of reconfigurable computing, except in special cases.

But you can read the literature and learn a lot more about this topic, and gain a deeper understanding about where it is likely to be useful and where it is not.
> 0 votes

---
Tags: computer-architecture, compilers, program-optimization
---


# Question
Title: Finding bicliques in a bipartite graph of minimum size
Let $G=(U \cup V, E)$ denotes a bipartite graph. A biclique $C = (U, V)$ is a subgraph of $G$ induced by a pair of two disjoint subsets $U' \subseteq U$, $V' \subseteq V$, such that $\forall u \in U', v \in V': (u, v) \in E$.

Given $\delta$, I'd like to identify bicliques $(U',V')$ such that $|V'| \ge \delta$. Since the number of all bicliques in a bipartite graph w.r.t its size can be exponential, I'm looking for **an approximate algorithm** (desirably with guarantees), that can find bicliques such that $|V'| \ge \delta$. For example, **find $k$ bicliques where $|V'| \geq \delta$**, in time polynomial w.r.t. $k$ and $G$. Can anyone suggest such an algorithm?

One naive solution is to enumerate bicliques using an enumeration-based algorithm and keep the bicliques that satisfy the last condition until the selection of "k" bicliques.

# Answer
> 2 votes
Here is an algorithm with $O(n^{2+\lg k})$ running time. It's not polynomial in $k$ and $n$, but for fixed $n$ it is polynomial in $k$, and for fixed $k$ it is polynomial in $n$. Here is the algorithm:

1. Let $\gamma = \lg k$.
2. Find all bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$. Output $k$ of them (stop early once you have found $k$ of them).

In step 2, it's easy to find all bicliques such that $|U'| \le \gamma$, $|V'| \ge \delta$ in $O(n^{2+\gamma})$ time: just enumerate all possibilities for $U'$. By the definition of $\gamma$, this takes $O(n^{2+\lg k})$ time, since there are only ${|U| \choose 0 } + \dots + {|U| \choose \gamma} = O(|U|^{\gamma}) = O(n^{\gamma}) = O(n^{\lg k})$ possible subsets $U'$ of size $\le \gamma$.

But will step 2 find enough bicliques? You might worry that it will find fewer than $k$ bicliques, even when there are at least $k$ in the graph. Not to worry; that can't happen. In particular, I'll show that if there is a biclique that is too large to be found in step 2, then there are at least $k$ bicliques that are small enough to be found in step 2, so step 2 will find enough to output $k$. The only way that step 2 can fail to output $k$ bicliques is if the graph does not contain $k$ bicliques.

Let's prove that claim. If step 2 outputs fewer than $k$ bicliques and there exists a biclique that the algorithm didn't output, that means there exists a biclique with $|U'| \ge \gamma+1$ and $|V'| \ge \delta$. What are the consequences of this? Well, there are two cases, depending on the size of $U'$:

* Case 1. Suppose $\gamma+1 \le |U'| \le 2\gamma$. Then you can find at least $2^{\gamma}$ more such that $|U'| \le \gamma$ and $|V'| \ge \delta$. Why? Well, take any subset of $U'$ of size at most $\gamma$, and keep $V'$ unchanged. Then this will give a new biclique, and it will meet all the conditions of the original problem. The number of such subsets is ${|U'| \choose 0} + {|U'| \choose 1} + \dots + {|U'| \choose \gamma}$, which is at least $2^{U'}/2$ (since $\gamma \ge |U'|/2$). Now $2^{U'}/2 \ge 2^{\gamma+1}/2 \ge 2^{\gamma} \ge k$, so this gives us $k$ more bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$. Thus in this case there exist enough bicliques that step 2 can find $k$ of them.
* Case 2. Suppose $|U'| \ge 2\gamma$. Then you can find at least $2^{\gamma}$ more bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$. Why? Again, take any subset of $U'$ of size at most $\gamma$; that will lead to another biclique that can be found in step 2. How many such subsets are there? There are at least ${|U'| \choose \gamma}$ of them, and ${|U'| \choose \gamma} \ge (|U'|/\gamma)^{\gamma}$ more (see the first bound here). By assumption, $|U'|/\gamma \ge 2$, so this means there are at least $2^{\gamma}$ more such subsets, i.e., at least $2^{\gamma}$ more bicliques that can be found in step 2. Thus in this case there exist enough bicliques that step 2 can find $k$ of them.

In either case, if the graph has at least $k$ bicliques, this algorithm will output at least $k$ of them.

---
Tags: graphs, approximation, clique
---


# Question
Title: Is the problem of traversing every vertex of a graph (not necessarily once) without crossing an edge more than once in P?
I know that finding a Hamiltonian circuit is in NP and I know that finding an Eulerian circuit is in P. However, what about the following problem:

* Must leave the starting vertex and visit every other vertex;
* You may only return to the start after visiting every other vertex;
* You can visit the same vertex multiple times, as long as it's not the starting vertex;
* You don't have to use every edge in the graph, but each edge can only be used once.

Is that in P or NP-hard? I tried different approaches to this but now I don't know if I'm wasting my time in case this problem doesn't have an efficient solution.

# Answer
> 3 votes
This problem is NP-hard.

Consider the following variants:

**Variant 1:** given a graph where each vertex has degree at most three, determine if there is a Hamiltonian path.

**Variant 2:** given a graph, determine if there is a trail (a path without repeated edges) that visits every vertex at least once.

Variant 1 is NP-hard \[1\].

Variant 1 can be reduced to variant 2 by mapping to the same graph.

If there is a Hamiltonian path on the graph, the Hamiltonian path is certainly a trail that visits every vertex at least once.

On the other hand, if there is a trail from $u$ to $v$ that visits every vertex at least once, since every vertex in the graph has degree at most three, every vertex except $u$ and $v$ must appear exactly once on the trail. If every vertex appears exactly once, the trail itself is a Hamiltonian path. If $u$ and/or $v$ appear twice, remove the first and/or the last edges on the trail respectively, then the trail becomes a Hamiltonian path. Anyway there is a Hamiltonian path in the graph.

So variant 2 is NP-hard.

---

Suppose the problem in OP is in P. Given an instance of variant 2, construct a new graph for every pair of vertexes $(u,v)$ by adding a new vertex $s$ and new edges $(s,u)$ and $(v,s)$. Now there is a trail that visits every vertex at least once in the original graph if and only if the answer to the problem in OP on at least one of these new graphs is "yes". So one can solve variant 2 in polynomial time by solving the problem in OP on these new graphs. So the problem in OP is NP-hard.

---

<sub>\[1\] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", *Proc. 6th ACM Symposium on Theory of Computing (STOC '74),* pp. 47–63, doi:10.1145/800119.803884.</sub>

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


# Question
Title: How to prove that non-antipodal vertices cannot be a diameter of a convex polygon?
I am learning Shamos's rotating calipers algorithm for finding the diameter of a convex polygon in his Ph.D. thesis; Page 78.

It reads

> Consult Figure 3.23 and notice that parallel lines of support cannot be made to pass through every pair of points. For example, no lines of support through vertices $D$ and $F$ can be parallel. *This means that $DF$* is not a diameter. A pair of points that does admit parallel supporting lines will be called *antipodal*.

***Problem:*** How to prove that non-antipodal vertices cannot be a diameter of a convex polygon?

***My Informal Attempt:*** See Figure 3.23. Intuitively, by rotating the line $DC$ about $C$ and then $CB$ about $B$, we can get two parallel lines of support passing through $F$ and $B$. However, is $FB$ necessarily longer than $FD$? If so, how to prove it?

---

> A line $L$ is a ***line of support*** of a convex polygon $P$ if it meets the boundary of $P$ and $P$ lies entirely on one side of $L$. (Definition 3.6; Page 69)

# Answer
I find it easier to prove the equivalent statement 'any pair $A,B$ such that the segment between them is a diameter of $P$ must be anti-podal':

If the segment $s$ between $A,B$ is a diameter, construct the lines $k,l$ as follows: line $l$ is the unique line perpendicular to $s$ and through $A$. Line $k$ is the unique line perpendicular to $s$ and through $B$.

I claim that the lines $l,k$ are parallel lines of support. These lines are parallel, as they are perpendicular to the same segment. To see that they are lines of support, suppose to the contrary that $l$ is not a line of support. As $A$ lies on the boundary of $P$ and in $l$, $l$ intersects the boundary of $P$. So $l$ can only *not* be a line of support if it intersects the interior of $P$. But this means that there is a point $X$ in $P$ ('beyond' the line $l$) such that $|XB|\>|AB|$, contradicting the fact that $s$ is a diameter of $P$!

So $l$ is a line of support. Analogously, $k$ is a line of support as well. So, as there is a parallel pair of lines of support through $A$ and $B$, $A$ and $B$ are anti-podal.

$\square$

The picture below sketches the situation where $A,B$ are endpoints of a diameter of $P$. A position where the hypothetical point $X$ could lie is also shown (it is clear that here there can be no point $X$ such that it lies in $P$!) Note that while $C,D$ are *not* endpoints of a diameter, they are anti-podal!

##

Be careful though, as the converse of the statement, 'Any segment such that the endpoints $A,B$ of that segment are antipodal in $P$ is a diameter in $P$' is false. As a counterexample, take a (non-square) kite (or take the sketch above). Clearly, the two pairs of opposing corners are anti-podal, but only one of the segments between the pairs is a diameter! Your informal attempt seems to try to prove this. As what you're trying to prove is false, it isn't surprising that formalizing the proof fails!

---

Note that I don't use the fact that $P$ is convex. You can check that this proof also works for non-convex, but simple polygons (it might even work for non-simple polygons, but these things are awful, so I'd rather not make claims about them). Note that in the case of convexity, the diameter need not necessarily be contained within the polygon, but all definitions still apply.
> 1 votes

---
Tags: computational-geometry, convex-hull
---


# Question
Title: Computer vision methods without "pre-training"
I'm new to computer vision and I have a common question that I couldn't figure out with Internet or books. As I understood, in general, there are two main approaches in modern computer vision: neural networks based methods and more "classical" methods that use feature extration (edges, keypoints, gradient and etc), like edge detectors, HOG, SIFT and others.

In case of neural networks everything is clear: we have a networks and we use datasets to train it. In other words, we can't use neural networks without previous training it (I call it "pre-training").

And as I understood, we have a bit different situation with features based methods. All examples and techniques that I have already seen consist of two steps. At first, we extract features (maybe with scene pre-processing), and then we use a classifier to recognize the object by those features. If we want classifier to work, we need to train it. So, again, like in case of neural network, we need pre-training.

My question is: are there any computer vision methods that don't need pre-training? Of course, maybe we can use something like a custom, or sometimes "naive" algorithm for certain situation, but are there more common methods? And another related question - are there any methods that can tell us just if the scene contains object, without telling were is it and what kind of that object class is it, again, without pre-training?

Thanks for all answers!

# Answer
Yup, there are lots of them. For example, image segmentation through graph cuts, camera calibration, image morphing, image stitching, reconstruction of a 3D scene from multiple 2D images, optical flow algorithms, motion tracking, image restoration and inpainting, and probably many more.
> 1 votes

---
Tags: neural-networks, computer-vision, pattern-recognition, features
---


# Question
Title: Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?
This "research vignette" (whatever that is) claims that the polynomial hierarchy

> classifies problems according to a natural notion of logical complexity, and is defined with an infinite number of levels: problems at the zeroth level are the “easiest”, and for every integer $k$, problems at the $(k+1)$-st level have logical complexity “one notch higher” than those at level $k$.

Obviously this is just a heuristic explanation rather than any kind of rigorous claim, but is it true that problems higher in the hierarchy should be thought of as harder than problems lower in the hierarchy?

For example, consider the complexity class BQP. It is not believed to contain NP; in fact, many experts consider (Fig. 3) NP-complete problems to be *much* harder than the hardest problems in BQP. But the same experts also believe that BQP is not contained within the polynomial hierarchy PH (with Recursive Fourier Sampling as a concrete example of a problem believed to be in BQP \ PH). It therefore seems reasonable to say that for any $n$, there exist problems in $\Sigma\_n \setminus \Sigma\_{n-1}$ that are easier than RFS.

But putting these two results (that any NP-complete problem is harder than RFS, and that RFS is harder than some problem in $\Sigma\_n \setminus \Sigma\_{n-1}$ for any $n$) together, we find that there are problems in $\Sigma\_1$ (namely, any NP-complete problem) that are harder (in fact, *much, much* harder) than certain problems in $\Sigma\_n \setminus \Sigma\_{n-1}$ for all $n$. Therefore, I don't see any way in which the polynomial hierarchy actually ranks problems by complexity.

Is there is mistake in my reasoning? Is there any useful sense in which problems higher up in the hierarchy are always harder than problems lower down? (I know this is a soft question, since there are different ways of formalizing the notion that one problem is "harder" than another. Maybe the answer is just that the PH is *one* way of ranking certain problems by difficulty, but not generally the best way.)

# Answer
> 3 votes
The quote you give is an informal claim/intuition. Don't try to read too much into informal claims; they are intended to give you a sense of what's going on, but for specific details, you need to look at the precise technical claim.

I suspect the source of your confusion is that you are using the same phrase in two or three different ways in different places, without realizing it. This is the logical fallacy of equivocation. In particular, I don't think you're using "harder than" in exactly the same way each time you use it. This then leads to you reaching conclusions that seem absurd or confusing. One way to remedy the confusion is to understand more clearly exactly what you mean by "harder than", and then walk through your logic.

One possible meaning of "P is harder than Q" is that the "running time of the fastest algorithm to solve P is larger than the running time of the fastest algorithm to solve Q, in some specific theoretical model of computation". This is a statement about theoretical complexity. Note that this meaning depends on the model of computation. P might be harder than Q in one model of computation (e.g., classical computation), but not in another model (e.g., quantum computation).

A second possible meaning of "P is harder than Q" is "Q reduces to P". This is a theoretical statement, which has implications for the previous statement (if Q reduces to P, then the running time of the fastest algorithm for P can't be too much less than the running time of the fastest algorithm for Q). Note that this notion of "harder than" is as a partial order. There might be two problems P,Q such that neither "P is harder than Q" nor "Q is harder than P" are true; the problems might be incomparable.

A third possible meaning of "P is harder than Q" is "in practice it's probably harder (takes more time or costs more) to solve instances of P than instances of Q". This is a statement about engineering and what is feasible in practice, rather than theory. For instance, this will depend on whether quantum computers are feasible to build, in practice -- something that no one knows the answer to right now. If quantum computers are feasible, then we'll discover that factoring is much easier than all NP-complete problems, because a quantum computer can solve factoring quickly but can't solve NP-complete problems quickly (we think). If quantum computers aren't feasible, then factoring might turn out to be not much easier than some NP-complete problems.

Finally, just because a problem isn't in PH doesn't necessarily mean it is harder than all problems in PH -- so just because Recursive Fourier Sampling is not in PH doesn't necessarily mean it is harder than all problems in PH (in the sense of the existence of a reduction).

As a final complication, Recursive Fourier Sampling is a funny kind of problem. It's not an ordinary decision problem. Rather, it's an oracle problem. Oracle problems can't be directly compared to ordinary problems.

# Answer
> 0 votes
The answer to your actual question is yes. The only thing I would (nitpickingly) change about the text you cite is that, when it talks about the $(k+1)$-st level, it should acknowledge that it includes the $k$-th level. So the "one notch higher" happens only for problems that are new in the $(k+1)$-st level.

One thing the polynomial hierarchy does not do is encompass all problems. It "classifies problems according to \[...\] complexity", but *only those problems, which it happens to contain*.

The popular conjecture seems to be that BQP is incomparable with PH. (There are problems in NP which are conjectured not to be in BQP and problems in BQP which are conjectured not to be in PH.) And that is not even surprising. PH and BQP extend P in different ways. PH by (bounded-alternation) nondeterminism, BQP by quantum. A priori there is no reason to assume the resulting classes to be comparable.

---
Tags: complexity-theory, np-complete, complexity-classes, quantum-computing
---


# Question
Title: Why is the set for which a decision problem is true called a "language"?
When we have a decision problem, " does $f(x)=1$ hold?", we call the set of strings $x$ for which the answer is yes a "language".

Why this strange terminology?

# Answer
I believe a lot of this came out of linguistics research. People wanted to write down a formal description (grammar) of, e.g., the English language. By extension, the set of strings defined by *any* grammar is a language and, since unrestricted grammars are Turing-powerful, any computable set of strings is the language of some grammar.
> 14 votes

# Answer
I think it is useful to note that most pioneering CS work, such as initial work by Turing and Church, had the intention to describe computation carried out by *humans*. (Recall that a *computer* was a human profession around that time!)

From this perspective, the set of strings that are output of a decision problem is the set of strings that a (precise and correct!) human 'computer' may 'utter' (i.e. output, most likely the computer would write his/her answers down).

Calling this set of strings that refers to structured, but human, communication a 'language' doesn't sound very far-fetched to me, so this could be a reason for the term.

My knowledge of history isn't good enough to check whether this is merely my interpretation or the common interpretation at the time, so take this with a grain of salt. Still, I hope this provides *a* reason to name the concept a 'language'.
> 5 votes

# Answer
From Wikipedia, “a formal language is a set of strings of symbols together with a set of rules that are specific to it.” To precisely specify what we are trying to decide, ambiguous natural languages won’t do, so instead mathematicians represent possible inputs with precise symbols. Together, the set of strings that result in Yes outputs comprise, in a poetic sense, the language of that problem, *e.g.*, how 2, 3, 5, 7, and so on are the language of prime numbers.

Again according to Wikipedia

> The first formal language is thought to be the one used by Gottlob Frege in his *Begriffsschrift* (1879), literally meaning “concept writing,” and which Frege described as a “formal language of pure thought.”
> 1 votes

---
Tags: terminology
---


# Question
Title: How do you implement a language with greater capabilities using subordinate languages?
I've heard that C++ and Python where implemented using C. How can someone make an object oriented language out of something that doesn't support objects?

I've read in the book "Math You Can\`t Use - Patents, Copyright and Software" that code is considered an equivalent of mathematics because it will eventualy be ran on cirquits that work and interact based on mathematical logic.

If a limited tool like C can produce a tool with further capabilities like C++, does that mean that mathematics can be used to create "better" mathematics? That seems to contradict Gödel's incompleteness theorem.

What is the essence of this trancedance from simple procedural to object oriented? Is there some code written in C that C++ and Python use or are they written in a completely different paradigm from the ground up?

# Answer
> 3 votes
The key point is that essentially all programming languages are equally powerful, and as powerful as we know how to make any computing system. That is, they can all simulate a Turing machine, up to the limitations of the computer they're used on. (Real computers can run out of memory; Turing machines can't.)

The only differences between programming languages is in how convenient it is to express certain ideas. For example, you can implement objects in C using structs containing function pointers, though it's not very convenient because the compiler doesn't help you much so you have to do a lot of things manually that something like C++ would do automatically for you.

---
Tags: programming-languages, mathematical-programming
---


# Question
Title: Satisfiability where each clause contains almost all variables
Suppose that we have a CNF SAT instance where each clause contains all variables (i.e. in each clause for each variable either the variable or its negation is presented). Such problem can be trivially solved, since any such instance either contains all possible clauses or is satisfiable.

Question: is there some a similar (i.e. with bounded number of variables that are not presented in each clause) NP-complete problem?

# Answer
> 2 votes
Suppose every clause contains all but c variables. **I think the problem is in $P$**, which I believe can be seem from your example with $c=0$. In your case, every clause "forbids" exactly one satisfying assignment. Suppose we have $n$ variables, then the formula is satifiable when there is at least one satisfying assignment that remains, and thus, when not all $2^n$ possible assignments are forbidden.

I believe we can generalize this idea: keep a list of all such "forbidden" assignments: for each clause, add the $2^c$ assignments it forbids to the list (the opposite of the clause, with all possible extensions to the missing variables). If in the end, the list contains all $2^n$ assignments, the formula is unsatisfiable. Else, it is satisfiable

Note that this is polynomial time, if there are $m$ clauses, the list contains at most $2^c \cdot m$ forbidden assignments.

---
Tags: complexity-theory, satisfiability
---


title: Constructive Proof on Regular Languages

text:
# Question
Title: Constructive Proof on Regular Languages
As an assignment, I've to come up with constructive proofs for the following languages to be regular supposing A and B are two distinct regular languages.

$$L\_1=\\{w│w^R∈A\\}$$ $$L\_2=\\{w│w=a\_1 b\_1,…,a\_k b\_k;a\_i∈A,b\_i∈B\\}$$ $$L\_3=\\{xy│yx∈0A\\}$$ $$L\_4=\\{w│w∈A,∄y∈B:w=xyz for some x,z∈Σ^\* \\}$$ $$L\_5=\\{w│∃x∈B:wx∈A\\}$$

I've already come up with answers for the first two, but I've no idea about the rest. For L3 no information on what x and y are is provided, so I thought they must be strings concatenated together.

My main question is, is there any generalized algorithm which by using it one can derive an appropriate NFA or RegEx to prove that such languages are regular? Could these things be broken down into primitive structures or operators by some rules or methods so the corresponding NFA or RegEx for the constructive proof be derived from it?

# Answer
> 4 votes
In general, the answer is usually "no". Equality of languages is, most of the time, undecidable; regular languages are a special case here, at least when they are given in certain representations.

What you can do is to break down those languages in terms of *closure properties* of REG, e.g. reversal, homomorphism, complement, etc.

Since your task here is to *prove* such closure properties, you'll have to take the long and creative route: come up with a construction and prove it correct. The purpose of the exercise is to train doing exactly that, so taking a shortcut would be unwise.

# Answer
> 2 votes
If your task is to come up with constructions that find automata for the languages $L\_1$ to $L\_5$ given automata for $A$ and $B$, then I suggest to follow Raphaels advice and try the remaining cases. Think of what information to store in the states of the new automaton to make the new language. Most of these closure properties are considered somewhere on this site: reversal, shuffle, rotation, substring, quotient.

Now, if the question is philosophical, i.e., does there exist a powerful closure property that encompass all the closure properties from your exercise, in that case I have a suggestion.

Apart from the usual finite state automata, one also considers two-way finite state automata that may move in both directions over the tape. Shepherdson famously proved in 1959 that every two-way FSA can (constructively) be reduced to an ordinary one-way FSA.

Now consider automata with output, or better *two-way FSA with output* which we will call here 2NGSM. Let $T\_M(A) = \\{y\in\Sigma\_2^\* \mid \text{ for some } x\in A, M \text{ outputs } y \\}$. Those automata are quite powerful. (0) They can duplicate the input string by copying it twice to the output. (1) They can reverse a string by walking to the end of the tape and then returning to the beginning copying the letters to the output tape. (2) They can first write the letters at odd positions, write a special marker $\\#$, then write the letters at even positions in the string.

Then

* $T\_{M0}(A) = \\{ww\mid w\in A\\}$.
* $T\_{M1}(A) = \\{w^{R}\mid w\in A\\}$,
* $T\_{M2}((ab)^\*) = \\{a^n\\#b^n\mid n\ge0\\}$,

From these examples it is clear that while the input is regular, the output might not be regular. But it follows quite directly from Shepherdsons result that *inverse* 2NGSM do maintain regularity:

> If $B$ is regular, and $M$ is a 2NGSM, then $T^{-1}\_M(B) = \\{x\in\Sigma\_1^\* \mid \text{ on input } x, M \text{ outputs } y\in B \\}$ is regular.

Now $T\_{M0}$ above show the closure property root, $T\_{M1}(A)$ is reversal $L\_1$, and $T\_{M2}$ on target language $A\\#B$ solves your shuffle $L\_2$.

At this moment I can only solve $L\_3$ this way if $0$ is a special symbol that does not occur in $A$.

The last one $L\_5$ can be solved by constructing a 2NGSM $T\_B$ (actually one way) that on input $w$ concatenates an arbitrary $x\in B$ to $w$. Then $T^{-1}\_B(A) = L\_5$.

---
Tags: formal-languages, regular-languages, closure-properties
---


title: Psuedorandom Generator Classification

text:
# Question
Title: Psuedorandom Generator Classification
There are several pseudorandom number generators that we have no known polynomial time algorithms for inverting (finding the initial seed). Is it correct to say that inverting these generators is an NP problem?

# Answer
> 2 votes
NP contains decision problems. Problems with a yes or no answer. Finding $x$ such that $g(x) = y$ for some given pseudo-random generator $g$ and output $y$ isn't a decision problem. It's a function problem.
You can turn this into decision problem by asking whether the $i$'th bit of $x$ is 1 instead. Then you can still find $x$ by just asking this question once for every bit.
Now this problem of deciding on the $i$'th bit is trivially in NP. Speaking informally, every problem that has efficiently verifiable proofs is in NP. $x$ is just such a proof. You can quickly check it's $i$'th bit. And you can quickly check that $g(x) = y$.

---
Tags: complexity-theory
---


# Question
Title: How does the strong form of the PCP theorem imply the inapproximability of Max-XORSAT?
> > **Theorem 11.4** For any constant $\delta \> 0$, every problem in NP has probabilistically checkable proofs of length poly($n$), where the verifier flips $O(\log n)$ coins and looks at three bits of the proof, with completeness $1-\delta$ and soundness $1/2+\delta$.
>
> Moreover, the conditions under which Arthur accepts are extremely simple - namely, if the parity of these three bits is even.
> This theorem has powerful consequences for inapproximability. If we write down all the triplets of bits that Arthur could look at, we get a system of linear equations mod 2. If Merlin takes his best shot at a proof, the probability that Arthur will accept is the largest fraction of these equations that can be simultaneously satisfied. Thus even if we know that this fraction is either at least $1-\delta$ or at most $1/2+\delta$, it is NP-hard to tell which. This implies that it is NP-hard to approximate Max-XORSAT within any constant factor better than $1/2$.

First, I don't think it can be as simple as just checking that the parity is even. Merlin could just make Arthur accept anything by handing him a proof of all zeros, and make him reject anything with a proof of all ones. Surely the parity must instead equal some value that Arthur computes along the way.

Further, It's not a priori clear to me that Arthur would select every triplet with equal likelihood. If that wasn't the case, wouldn't it be possible for a no-instance to yield a Max-XORSAT formula where more than $1/2+\delta$ of the clauses can be satisfied even though Arthur accepts with probability less than $1/2+\delta$?

Let's take a degenerate case as an example. Arthur asks Merlin to help him decide whether a given sequence of $n$ bits $\mathbf{b}$ is all ones - $\mathbf{b=1}$ for short. This problem is trivially in NP. And Arthur clearly doesn't need Merlin's help. But he can go out of his way to use it anyway. Here's what they do:
First Merlin gives Arthur a PCP $\mathbf{x} \in \\{0,1\\}^n$ (let's assume $n \gg 3$). Then Arthur checks if $\mathbf{b=1}.$ If it is, he checks that $x\_1 \oplus x\_2 \oplus x\_3 = 1$ holds in Merlin's PCP. Otherwise, he checks either $x\_1 \oplus x\_2 \oplus x\_3 = 1$ or $\overline{x\_1} \oplus \overline{x\_2} \oplus \overline{x\_3} = 1$ (note that these can't both be satisfied) with equal probability 0.45. Or with probability 0.1 he checks $x\_i \oplus x\_j \oplus x\_k = 1$ for a uniformly random triplet.
Merlin can thus convince Arthur that $\mathbf{b=1}$ by giving him, for example, the proof consisting of all ones. But if $\mathbf{b\neq1}$ there's no proof that Arthur accepts with probability greater than 0.55. This gives PCP's with completeness $1-\delta$ (indeed we also have completeness 1) and soundness $1/2+\delta$ where $\delta = 0.05$.
Now what's the Max-XORSAT formula corresponding to $\mathbf{b\neq1}$? Well, Arthur could look at any triplet $x\_i, x\_j, x\_k$ as well as $\overline{x\_1},\overline{x\_2},\overline{x\_3}$. So presumably it's the conjunction of all those triplets when XORed together. All but one of these clauses can be satisfied. So the fraction is very close to one. But that's nowhere near the probability that Arthur will actually accept.

PS: We need a PCP tag.

# Answer
Theorem 11.4 states that for every $\delta \> 0$ there is a polytime computable function that on input $\varphi$ outputs a PCP (of a certain form) such that (i) if $\varphi$ is satisfiable then the cost of the PCP (to be defined) is at least $1-\delta$, and (ii) if $\varphi$ is unsatisfiable then the cost of the PCP is at most $1/2+\delta$.

The PCP consists of a distribution over quadruples $(i,j,k,b)$ where $i,j,k$ are indices in the range $1,\ldots,N$, for some $N$ depending polynomially on the size of $\varphi$, and $b \in \\{0,1\\}$. The value of an assignment $\alpha\colon \\{1,\ldots,N\\} \to \\{0,1\\}$ is equal to $\Pr\[\alpha(i) \oplus \alpha(j) \oplus \alpha(k) = b\]$, and the value of the PCP is the maximum value of an assignment.

(The version in which $b = 0$ always is easy to solve – the zero assignment has value 1. Similarly, when $b = 1$ the one assignment has value 1.)

Furthermore, the distribution is generated using $t = O(\log n)$ random bits. We can think of $i,j,k,b$ as functions of the randomness $r$.

Consider now the MAX-XORSAT instance $$ \bigwedge\_{r \in \\{0,1\\}^t} (x\_{i(r)} \oplus x\_{j(r)} \oplus x\_{k(r)} = b(r)). $$ Since $|\\{0,1\\}^t| = 2^t = 2^{O(\log n)} = \mathit{poly}(n)$, this instance has size polynomial in the size of $\varphi$.

The maximum fraction of constraints satisfied by this MAX-XORSAT instance is exactly the same as the value of the PCP. Hence if $\varphi$ is satisfiable, at least a $1-\delta$ fraction of constraints can be satisfied, whereas if $\varphi$ is unsatisfiable, at most a $1/2+\delta$ fraction can be satisfied.

An approximation algorithm for MAX-XORSAT with ratio strictly better than $1/2$ can distinguish between the two cases (for small enough $\delta$), and so can find out whether $\varphi$ is satisfiable or not. In other words, such an algorithm can be used to solve SAT.
> 3 votes

---
Tags: approximation
---


# Question
Title: Does godel's incompleteness theorem still hold if we have a TM that can do an infinity amount of computations?
I have heard whisperings that if we have a turing machine that is allowed to compute infinitely many steps in finite time, then we can solve the halting problem.

This made me wonder, if we have such a TM, do Godel's incompleteness theorems then not hold anymore?

My intuition is: If the TM can make an infinite amount of computations, it can simply check the truth-value of any formula, by checking all natural numbers. e.g. if we have a formula $\forall x \phi (x)$, the infinite-TM can simply check for every natural number $n$ whether $\phi(n)$ holds.

# Answer
> 4 votes
There is some ambiguity in how to define these new machines, essentially based on the question whether we can nest the "bursts of doing infinitely many steps in some finite time" or not. In the weakest interpretation, we essentially just get an oracle Turing machine with access to the Halting problem. In the strongest, we get the Infinite Time Turing Machines (ITTM).

Both machines can easily decide the ordinary Halting problem. However, the proof of non-computability of the Halting problem uses very little prerequisites. In particular, it shows that none of our machines can solve their own Halting problems.

So while an ITTM can decide truth of all basic arithmetic formulas (by just searching through the natural numbers whenever required), they cannot decide all $\Sigma^1\_2$-formulas. And to properly define and work with ITTMs, we need $\Sigma^1\_2$-formulas. So we have just pushed undecidability further out, but we have not removed it.

A $\Sigma^1\_2$-formula is one of the form $$\exists A \subseteq \mathbb{N} \ \ \forall B \subseteq \mathbb{N} \ \ \phi(A,B)$$ where $\phi$ is a formula which contains only quantification over numbers, but not over sets of numbers.

---
Tags: turing-machines, incompleteness
---


title: Parameters of a linear code

text:
# Question
Title: Parameters of a linear code
Consider the code $C=\\{c=(c\_1...c\_n): c \in \Bbb F\_q^n, c\_1=c\_n\\} \subset \Bbb F\_q^n$.

I was able to prove that the code is a linear code because it is closed under addition and scalar multiplication. Also, it is clear that the length is n.

However I am having a hard time with minimum distance, dimension, and size.

For minimum distance: I know that for a linear code the minimum distance is equal to the minimum weight, or number of places with nonzero entries, of all nonzero codewords in C. However, I think the minimum weight can range between 1 to n entries, so does this mean that the minimum distance is 1?

For dimension and size: I know that the dimension is the order of the basis for C. I think that the basis is $B=\\{10...01, 010...0, 001...0, ... , 0...010\\}$, and so the dimension would be $n-1$, but I am unsure on this. If the dimension is $n-1$, then the size would be $q^{n-1}$.

Any help is appreciated, thank you in advanced. Please also let me know if this post does not belong to this stack exchange.

# Answer
You're right, minimum distance is the minimal nonzero weight, thus 1.

*A basis* is what you gave. There are many bases. And youre right on size and dimension as well.

**Edit:** As pointed out in the other answer the distance is 2 if $n=2.$
> 3 votes

# Answer
There is one exception in which the minimum distance is unequal to 1, and this is in the case that $n=2$. Since this is the code $C=\\{ 00,11 \\}$.

For all the other cases:

For $n=1$: the code $C=\\{0,1\\}$ and thus having minimum distance 1.

For $n \> 2$: the codeword $c$ is in $C$ such that $c=(c\_1,...,c\_n)$ in which $c\_1=c\_n=0$ and there exists one $c\_i=1$ such that $1\<i\<n$.
> 1 votes

---
Tags: coding-theory
---


title: Union-Find link-by-rank preserve a root

text:
# Question
Title: Union-Find link-by-rank preserve a root
Suppose I have two union-find trees with roots $x$ and $y$ respectively. I want to join them in constant time (this is normally possible since I already "hold" the roots) but I need $x$ to be the root of the merged tree. I don't know what rank $x$ or $y$ have (or more precisely formulated I need this to work always - for any $x$ and $y$ I want the final tree to have $x$ as its root). Is that possible? I couldn't find a solution to this, but it's really not my day today :)

# Answer
> 1 votes
Unfortunately, that's not possible with the standard data structure for union-find (namely, with the union by rank method).

The data structure has invariants that in some cases require making $y$ be the root (namely, when $x$'s rank is smaller than $y$'s rank, you are required to make $y$ the root). If you force $x$ to be the root in such a situation, then you destroy the invariants, which might make subsequent Find/Union operations slow.

It sounds like you are thinking that perhaps we can reorganize the inner structure of the tree under $x$ or the tree under $y$. Unfortunately, it's not possible to do that in the standard Union-Find data structure. The data structure doesn't have child pointers (doesn't have any way to get from $x$ to its children, or from $y$ to its children), so there is no way for a data structure to change the inner structure of the tree under $x$ or the tree under $y$.

So if you want to achieve this, you will probably need an entirely new data structure. If so, you should probably ask a new question and specify your requirements in terms of the externally observable behavior of the API's, rather than in terms of the internal state of the data structure.

---
Tags: data-structures, union-find
---


# Question
Title: Union-Find with link-by-rank to represent a binary field with simple operations
I have a field $X$ of given length $n$ which is filled with zeroes in the beginning.

I only need these 3 simple operations:

GET\_VALUE$(i)$: returns the value of $i$-th cell ($X\[i\]$)

SET\_TO\_1$(i)$:basically $X\[i\] \leftarrow 1$ for $i \< n - 1$, otherwise nothing (the last cell of $X$ is always zero ($X\[n-1\] = 0$))

FIND$(i)$: find the least index $j \geq i$ s.t. $X\[j\] = 0$ (note that this operation will always succeed since the last cell is always zero)

I need the time complexity of operation GET\_VALUE to be constant. And both SET\_TO\_1 and FIND to be in $O(\log n)$.

My thinking so far:

I am almost sure the perfect data structure for this would be Union-Find, because sets elegantly represent all such $i$ that for which FIND returns the same value. The root of the sets would be the index that is returned by the FIND operation - the only index $i$ in the set s.t. $X\[i\] = 0$.

The implementation of GET\_VALUE operation would be also pretty straightforward. If $i$ is a root (points to itself) return $0$ and $1$ otherwise.

However this doesn't work nicely for the SET\_TO\_1 operation. I would want it in case it sets a cell $X\[i\]$ from $0$ to $1$ to join the set represented by the root $i$ to the next one (which contains the element of index $i+1$). But if I want GET\_VALUE to be in $O(\log n)$ I need to use link by rank and thus I cannot choose which root of the two unified trees is preserved - but in order for this to work it *must* be the second one (from the $i+1$ set).

How can I fix this?

# Answer
In each node store an additional field named "value". The value of a root $r$ represents $\text{FIND}(r)$ (so the root itself is not necessarily $\text{FIND}(r)$). For $\text{SET\_TO\_1}(i)$, let $r$ be the root of the tree $i+1$ belongs to, we in addition change the value of the new root to the value of $r$. Now which root becomes the new root does not matter at all.
> 4 votes

# Answer
This is an alternative implementation that does not use union-find. When compared to your implementation (with the tweak by xskxzr), my implementation has both advantages and disadvantages.

Advantages:

* It has a real $O(1)$ `GET_VALUE` instead of an amortized nearly-$O(1)$ one
* It could implement `SET_TO_0`, or even `SET_TO(i, n)` for any `n` (with `FIND` still returning the first non-zero value)

Disadvantages:

* Uses more memory
* Has a $O(\log n)$ `FIND` where yours is amortized nearly-$O(1)$

---

First, notice that you have one "set" operation (`SET_TO_1`) and two "get" operations (`GET_VALUE` and `FIND`). So you can have two structures that can handle `SET_TO_1`: one per get operation.

For `SET_TO_1` and FIND, a balanced binary search tree that contains the elements whose value is 0 (or 1 if you want to think a bit more and not have an $O(n)$ initialization) give `SET_TO_1` and `FIND` in $O(\log n)$.

So now we only need to handle `SET_TO_1` and `GET_VALUE`. For which an array clearly works.

In conclusion, your structure is a balanced binary search tree T and an array A. The tree is initialized as containing all the elements, and the array as filled with zeroes.

* `SET_TO_1(i)` does `T.remove(i)` and `A[i] := 1`
* `GET(i)` returns `A[i]`
* `FIND(i)` returns `T.myfind(i)` (where `myfind` find the smallest element `j` in the tree such that `i <= j`)

`myfind` could be implemented as follow:

```
function myfind(tree, index) {
  var node = tree;
  while (not isLeaf(node)) {
    if (index == node.value) {
      return index;
    } else if (index < node.value) {
      if (node.left != null) {
        node = node.left;
      }
    } else /* if (index > node.value) */ {
      if (node.right != null) {
        node = node.right;
      }
    }
  }
  // We now are at a leaf such that there is no value of the tree between index and node.value
  // Because of this, if index <= node.value, we are done
  if (index <= node.value) {
    return node.value;
  }
  // If index > node.value, we want to find the node right after the current node in an infix ordering of the tree
  // To do this, while we are the right child of our parent, we go up
  while (node == node.parent.right) {// node.parent can't be null, by (1)
    node = node.parent;
  }
  // here, node == node.parent.left and the leaf we started at is node.right.right.[...].right so the leaf is the last node in the infix traversal of node.parent.left, and so the next node is node.parent.
  return node.parent.value;
}

```

`(1)`: The only way for `node.parent` to become null at some point is that the leaf we started at is `root.right.[...].right`. We know that its value will be `n-1`, and that all other values will be smaller. In particular, if the `index` we have to `myfind` wasn't absurd, it was such that `index <= n-1` and so we returned at line 20.

---

The method of building two data structures for a signature and combining them can be used in many contexts: if you have two implementations of an interface with complexities (and a complexity of $+\infty$ to mean that the method is not implemented), you can combine them by taking both underlying structures, making "set" operations act on both (so that their complexity is the sum of the complexities of the two previous implementations) and the "get" operations use the fastest implementation of the two (so that the complexity is the min of the two complexities of the two previous implementations).
> 2 votes

---
Tags: data-structures, union-find
---


# Question
Title: A second question on "Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs"
Let B={M1,M2,...} be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent machine in C and vice versa.

I saw a hint on solving this question which is given in the following picture:

But I have a difficulty in constructing such enumerator $E\_{0}$, Also how will I show that every machine described in $B$ has an equivalent machine in $C$ and vice versa, could anyone help me in doing so?

Also it is worth to say that the solution of this problem is found here:

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

But I could not understand it. could anyone explain the solution for me in a simple way ? and in a way depending on the above hints?

# Answer
> 1 votes
Recall the padding lemma: given $\langle M \rangle$ we can compute $\langle N \rangle$ where $N$ is equivalent to $M$, but has a longer representation. (Essentially, we can always add more irrelevant states to a TM, effectively.)

Then, define $E\_0$ to do the following:

* Run $E$ until $M\_1$ is produced.
* Let $N\_1 = M\_1$
* Output $N\_1$
* Continue running $E$ until $M\_2$ is produced.
* Let $N\_2$ be $M\_2$, after as many paddings as needed to make its representation larger than $N\_1$.
* Output $N\_2$
* Continue running $E$ until $M\_3$ is produced.
* Let $N\_3$ be $M\_3$, after as many paddings as needed to make its representation larger than $N\_2$.
* Output $N\_3$
* And so on.

By construction, $E\_0$ prints larger and larger strings, hence its enumerated language is decidable: this is the wanted language C.

We now need to check the quivalence. For any $N\_i$ in the language enumerated by $E\_0$, we find an equivalent $M\_i$ enumerated by $E$. Vice versa, for any $M\_i$ in the language enumerated by $E$, we find an equivalent $N\_i$ enumerated by $E\_0$.

---
Tags: formal-languages, turing-machines, computability, undecidability
---


# Question
Title: Proving that EXP doesn't have polynomial-size circuits
How to prove for all $i\in\mathbb{N}$, there exists a language $A\in\mathrm{EXP}$ such that no family of boolean circuits of size $n^i$ decides $A$?

I have a reminder that says $$ \mathrm{EXP} =\bigcup\_{c\in\mathbb{N}} \mathrm{DTIME}\left(2^{n^c}\right). $$

Thought of building a TM that on input $x$ of size $n$, finds a function $f\_{n}$ such that there is no circuit of size $n^k$ that calculates it. Go through all functions and for each one go through all the circuits and check whether they calculate the function. If none of them calculates it then it's what we want.

I don't know how to show this is $\mathrm{EXP}$ or how to prove this solves the problem.

# Answer
You can consider a circuit as a directed graph where nodes are inputs and gates. For a circuit of size $n^k$ on input of size $n$, there are at most $(n+n^k)^2$ edges, and each node (gate) has three possibilities, so the number of such circuits is at most

$$3^{n^k}\cdot2^{\left(n+n^k\right)^2}=O\left(2^{n^{2k+2}}\right).$$

So you need only to enumerate at most $O\left(2^{n^{2k+2}}\right)$ functions. In addition, checking whether a circuit of size $n^k$ calculates a function costs $O(n^{2k}2^n)$ time since computing on each input costs $O(n^{2k})$ time (here we compute the running time under a RAM rather than a TM without loss of generality) and there are $2^n$ inputs. Note for each function, you need to go through all circuits, and for each circuit, you need to check whether it calculates the function, so the total running time of the RAM on input of size $n$ is

$$ O\left(2^{n^{2k+2}}\right)\cdot O\left(2^{n^{2k+2}}\right)\cdot O(n^{2k}2^n)=O\left(2^{n^{2k+4}}\right). $$

So the language decided by this RAM is in $\mathrm{EXP}$ (note $k$ is a fixed constant). Obviously no family of circuits of size $n^k$ decides this language by the construction of the RAM.
> 4 votes

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


# Question
Title: How to reduce halting problem to the problem of whether a Turing Machine accepts infinitely many inputs?
The language $\\{w \mid w \in \\{0,1\\}^{\*}\text{ and }M\_w\text{ accepts infinitely many inputs}\\}$ is undecidable, where $M\_w$ is the Turing machine represented by $w$.

I am confused because I do not know how to reduce this problem. Maybe it works with the complement of the Halting problem?

# Answer
If it is decidable, let $M$ decide it.

Construct a decider $D$ that works on input $\langle w\_1,w\_2\rangle$ as follows:

1. Construct $M\_w$ (as well as its encoding $w$) that works on input $x$ as follows:

1. Run $M\_{w\_1}$ on $w\_2$.
    2. Accept.
2. Run $M$ on $w$.
3. If $M$ accepts, accept; otherwise, reject.

We can see $D$ accepts if and only if $M$ accepts $w$, i.e. $M\_w$ accepts infinitely many inputs, which means $M\_{w\_1}$ halts on $w\_2$. Therefore $D$ is a decider for the halting problem, a contradiction.

Hence the language given in OP is undecidable.
> 1 votes

---
Tags: turing-machines, reductions, undecidability, halting-problem
---


# Question
Title: How to efficiently compute the most isolated point?
Given a finite set $S$ of points in $\mathbb R^d$, how can we efficiently compute a "most isolated point" $x\in S$?

We define a "most isolated point" $x$ by

$$x = \arg\max\_{p \in S} \min\_{q \in S \setminus \\{p\\}} d(p,q)$$

(I used the $x=\arg\min$ notation even though it is not necessarily unique. Here $d$ denotes the euclidean distance.) So in other words we're looking for a point with the largest distance to the closest neighbour.

A naive algorithm would be computing all pairwise distances, finding the neighbour with the least distance for every point and then finding the maximum of these. This is takes $O(n^2)$ operations, but can we do better than that?

# Answer
> 1 votes
Use any algorithm for all nearest neighbors; then you can trivially solve your problem. Such an algorithm finds, for each data point, its nearest neighbor. The most isolated point is the one whose nearest neighbor is farthest away, so once you've solved all nearest neighbors, you can find the most isolated point by a simple linear scan.

Apparently all nearest neighbors can be found in $O(n \log n)$ time; see the references on Wikipedia. Or, if you want something to implement, take any data structure for nearest neighbors, and for each point $p$, find its nearest neighbor.

# Answer
> 0 votes
As suggested in the comments I would look into nearest neighbor queries.

Doing one NN-Query per point should be in the order of $O(n\* log (n))$ so it is already better than the naive solution.

You can further improve that by adding a parameter to the NN-Query that contains the nearest neighbor distance $d\_{max}$ of the most isolated point that you found so far. You can then abort any NN-query as soon as it finds a point that is closer than $d\_{max}$. This should speed up your search quite a bit.

Btw, people often suggest KD-Trees for NN-Search. KD-Trees are very easy to implement but in my experience consistently scale less well with higher dimensions than other trees. For $d \> 10$ or so I would recommend using an R-Tree, such as R\*Tree (R-Star-Tree), X-Tree or STR-loaded R-Tree, or an PH-Tree (which is more like a bitwise quadtree).

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


# Question
Title: How is density of a substance in grams per cubic centimeter a discrete attribute?
I'm going over the different types of attributes in data-mining (nominal, ordinal, discrete, etc) and there is one example in the book that states that the density of a substance in grams per cubic centimeter is a discrete attribute. Why is this? I confuses me that this is the case but it also says that the distance from the center of campus is continuous.

# Answer
> 0 votes
The book is wrong. Density is continuous. It could be any real number. You are quite right.

---
Tags: data-mining
---


# Question
Title: Trustless exchange without a third party
Is there a cryptographic (or even not entirely cryptographic) way of exchanging objects between Alice and Bob that would not require a third party, and Alice and Bob would not need to trust each other? For example, Alice and Bob have Y and X objects (some information) and want to exchange them (in other words both Alice and Bob after transaction will have access to the set Y∪X). How can they do this directly to each other? Is it possible to solve this problem, for example, using private keys, zk-proofs, etc? Is it possible to solve it in principle? Thank you!

# Answer
> 1 votes
This is known as the fair exchange problem. There's lots of research on the topic; see the link for an overview and starting point.

---
Tags: cryptography
---


title: Knapsack problem question

text:
# Question
Title: Knapsack problem question
Based on this video, the tutor explains the knapsack problem with dynamic programming approach. One thing is not cleared in this video, which is my main question.

All the values on the first row (except 0) are set to 1 because value and weight (on that row) are 1 hence, we cannot exceed that number

Below is the complete example of the tutor as linked in the above video.

My question:

> -What would be the values of the **first row** if weight and value were not **both** the **same**?

So let's say value is **25** and weight **3** (first row values): I suppose the first row results would be `0,25,25,25,25,25,25,25`

Let me know if i am wrong. Thank you.

Note that the first row is important to be correct as every row depends on the previous one. The tutor's example in the video, is not the best as the first row value and weight are both 1.

# Answer
> 2 votes
First row indicates the optimal knapsack for each weight using only that item. Then each subproblem in that row asks what is the maximal value one can reach with using only first item and maximum weight indicated by the columns. Then because your first item would have a weight of 3, there is no way for you to include an item for any total knapsack of weight less than 3. Therefore the optimal knapsack for each weight less than 3 would be 0.

Then the first row would look like: 0 0 0 25 25 25 25 25

---
Tags: algorithms, dynamic-programming, knapsack-problems
---


# Question
Title: Logical and non logical symbols and predicates
I am going through the text from "R.Brachmann and H.Levesque: Knowledge representation and reasoning". Here it has been described(in page 15) that there are two types of symbols : the logical symbols and the non logical symbols.

Logical symbols are the ones that have a fixed meaning and the non logical ones are the ones having application dependent meaning.

What I find confusing is "variables" having classified as logical ones whereas functions symbols have been classified as non logical ones.

I don't know whether I should be confusing this with the context of programming languages or not but variables also don't have fixed meanings and they too are created for application dependent use.

Shouldn't they both be in the same slot?

Now for predicates, I do not understand what exactly is a predicate? Do predicates mean the same thing as relations like "greater than", "less than"? If yes, then can there be an infinite variety of predicates? I can think of only this "lesser than ", "greater than", "equal to". What are some more examples of predicates?

P.S : Sorry about the predicate part , perhaps the following link contains a lot about it : https://stackoverflow.com/questions/6337778/predicate-vs-functions-in-first-order-logic

# Answer
> 1 votes
A predicate is basically a set or a function from your universe $A$ to $\\{0, 1\\}$ (belongs to the set or not). More examples for that are edge relations or any kind of property you can assign to an object (e.g. male, female when $A$ is the set of all humans).

In FO you can distinguish non-logical symbols from logical symbols by looking at their interpretations via a structure. Constants, functions, and relations are assigned by this structure. Variables are not non-logical symbols because they do not change their meanings when you vary the structure you use for the interpretation of the formula. However, they also have no fixed meaning (compared to $\exists, \wedge, \neg, \ldots$), so you do not have to count them as logical symbols either.

You can probably find other sources, where variables are treated differently.

---
Tags: first-order-logic
---


# Question
Title: What is the fastest online sorting algorithm?
Quoting Online algorithm from Wikipedia:

> In computer science, an online algorithm\[1\] is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.

One is Insertion Sort, but it runs in horrible $O(n^2)$ time.

# Answer
I suggest Tree Sort, variant with self-balanced tree. In this case complexity is $O(logn)$ (per insertion).
In that case you can access sorted structure at any time.

If inputs comes in batches, sort batch (with any fast algoritm) and then merge.

Other algorithms will also suffer from divided input, but insertion sort is poor even if input is available at once.

Natural split into sorted parts occurs in Mergesort and Timsort. But overall performance should be adjusted to needs: if data comes one at the time, but there is no need to retreive sorted version, it would be nice to keep smaller sorted buffers.
When length of array is known in advance and distribution the set it is possible to do distribution based sort, it spares some empty cells for incomming data.
If data could be divided into ranges, this would enable partitioning of data as it arrives.
> 12 votes

# Answer
Heapsort is O(nlogn), but with a heap you can insert each element with O(logn). The benefit of this is that you always have access to your max and minimum element and can access them in O(1) time.
> 4 votes

# Answer
Depends on how you measure fast. Are you interested in squeezing out milliseconds or just in big O running time?

Insertion's sort O(n^2) may not be as horrible as it may seems with proper implementation. If you use binary search for finding the the insertion point your comparisons go down to O(log n) and if you move memory efficiently you can squeeze out quite a bit of performance.

For comparison on my system binary search saves about a second and a half for sorting 40 000 ints.

```
$ ./engine.exe 40000

binary_insertion_sort()
Swap: 399585418 swaps
Comp: 596083 comparisons
Time: 14.566 sec

insertion_sort()
Swap: 399585418 swaps
Comp: 399625411 comparisons
Time: 16.119 sec

```

Similarly, moving 100 000 000 ints one to the left takes 0.5790s with a for loop and only 0.2180s with memmove().

Depending on the size of your data set and the architecture you're running it on it may prove perfectly usable, especially online.

Not all O(n^2) algorithms are created equal, even though they are still O(n^2) at the end of the day.
> 3 votes

# Answer
The time is $O (n^2)$, but only with the usual definition of "sorted": That we have an array of consecutive elements in ascending order. With that data structure, adding another element even if we know exactly where it belongs, takes time proportional to n on average, because in an array we have to move all elements along to insert one.

If we redefine sorted as "there is a way to traverse all items in ascending order quickly", then we can have for example a sorted tree much faster than $O (n^2)$.
> 1 votes

---
Tags: algorithms, sorting, online-algorithms
---