# Question
Title: Does there always exist an optimal solution to the metric steiner tree problem which doesn't contain any steiner nodes?
Given an undirected graph with nonnegative edge weights and a partition of the vertex set into terminals and Steiner vertices, the Steniner tree problem consists in finding a minimum weight tree in the graph that contains all terminals and any subset of the Steiner vertices.

The metric steiner tree problem is when the edges satisfy the triangle inequality. Would this not imply that for every instance of the problem, there exists an optimal solution containing no Steiner vertices (since you can shortcut the path containing the Steiner vertex down to a path with just terminals, without increasing the weight)?

# Answer
> 2 votes
No. The problem is that a single Steiner vertex can be involved in multiple of these shortcut operations. In the first shortcut operation, the total weight of the edges decreases (at the cost of disconnecting the tree), but not necessarily in later shortcut operations, as then you are shortcutting a path of which some edges may already have been removed.

Concretely, there are instances where not using Steiner vertices is suboptimal. For example: let the terminals be the three vertices of an equilateral triangle with side-length $1$ and a Steiner vertex at the center of the triangle. All vertices have an edge, with the weight equal to their Euclidean distance. If we do not use the Steiner vertex, then the tree consists of two sides of the triangle, and its weight is $2$. However, the star centered at the Steiner vertex in the middle of triangle has weight $\sqrt{3} \< 2$ (as the distance from a vertex of a triangle to its center is $\frac{1}{3}\sqrt{3}$)

# Answer
> 2 votes
Steiner nodes give more freedom to make shortcuts so they cannot lead to worse solutions. And it is easy to find examples where they give better solutions.

In fact, Steiner points have been introduced just for that purpose.

---
Tags: optimization, trees, computational-geometry
---


title: Intersection of different languages

text:
# Question
Title: Intersection of different languages
Consider L1 = Any language generated by a machine M1

L2 = Any language generated by a machine M2

Machine can be – FA, PDA, LBA, or TM

Assuming Machine M2 is more powerful than M1

Let **L3 = L1 $\cap$ L2**

Now can we **always** say that L3 can be generated by Machine M2 ?

For **eg:**

**L1** = Any Context Free Language (i.e Generated by NPDA)

**L2** = Any Recursively enumerable language (i.e Generated by TM)

Now can we always say that L1 $\cap$ L2 is Recursively Enumerable Language i.e it can be generated by a TM?

# Answer
> 1 votes
Nope. For several examples, see https://en.wikipedia.org/wiki/Context-free\_language#Nonclosure\_under\_intersection,\_complement,\_and\_difference, Which closure properties are always valid between regular, context-free and non context-free languages?, Intersection of Deterministic Context-Free Languages.

# Answer
> 1 votes
A general principle that may help:

* Deterministically-defined language classes (e.g., Regular, Turing-decidable), are typically closed under union, intersection, and complement.
* Nondeterministically-defined language classes (e.g., Context Free, Turing-recognizable) are typically closed under union, but not intersection and complement.

By "deterministically-defined", I mean that the computational model is deterministic, it processes the input in some way, always terminates, and deterministically produces an output. By "nondeterministically-defined", I mean that the computational model involves either nondeterminism in the way the rules are applied or nontermination.

Of course, this rule is only a starting point. Sometimes, the computational model admits determinization (e.g., NFAs can be determinized to DFAs) in which case the nondeterminism is not actually inherent to the model.

---
Tags: automata, closure-properties
---


# Question
Title: Is shadowing of the type variable allowed in System F second order abstraction?
I'm reading *Type Theory and Formal Proof* by Nederpelt and Geuvers. Chapter 3 is about $\lambda 2$ and $\Pi$-Types (aka System F, I think?) and the derivation rule for 2nd order abstraction seems to forbid "shadowing" of the type variable; i.e. in context $\Gamma \equiv \alpha : \*$ it is not possible to derive a term of type $\Pi \alpha : * . \alpha \rightarrow \alpha$. This is because the premise of $abst\_2$ in Figure 3.1 page 76 has context $\Gamma, \alpha : \*$ and definition 3.4.4 of $\lambda 2$ context at page 75 explicitly says that $\Gamma, \alpha : * \equiv \alpha : \*, \alpha : \*$ wouldn't be a valid context. First obvious question is: did I understand correctly? If yes, then the second question is why? Even in C++ I can do it...

```
struct alpha {};

template <typename alpha>
alpha id(alpha x) { return x; }

```

## Edit

I just realised that someone who doesn't have the book might struggle to follow my question. So here's more context. The derivation rule for 2nd order abstraction says:

$$ \frac {\Gamma, \alpha : * \vdash M : \sigma} {\Gamma \vdash \lambda \alpha : * . M : \Pi \alpha : * . \sigma}; $$

a valid $\lambda 2$ context is also recursively defined as:

1. the empty context $\emptyset$ with an empty domain, i.e. $\texttt{dom}(\emptyset)=()$;
2. if $\Gamma$ is a valid context, and $\alpha$ is a type variable (i.e $\alpha \in \mathbb{V}$) such that $\alpha \notin \texttt{dom($\Gamma$)}$, then $\Gamma, \alpha : \*$ is a valid context with $\texttt{dom}(\Gamma, \alpha : \*) = (\texttt{dom}(\Gamma), \alpha)$;
3. if $\Gamma$ is a valid context, $\rho$ is a type (i.e. $\rho \in \mathbb{T}$) such that $\alpha \in \texttt{dom}(\Gamma)$ for all free type variables $\alpha$ occurring in $\rho$, and if $x \notin \texttt{dom}(\Gamma)$, then $\Gamma, x: \rho$ is a valid context with $\texttt{dom}(\Gamma, x: \rho) = (\texttt{dom}(\Gamma), x)$.

So if my goal is to derive some $M : \Pi \alpha : * . \sigma$ and my current context is $\Gamma \equiv \alpha : \*$ then the premise of the 2nd order abstraction rule would be $\alpha : \*, \alpha : \*$ which is not a valid context according to the definition of context just given.

# Answer
> 3 votes
Just because two variables have the same name doesn't mean they're the same variable. Shadowing happens when two variables have the same name in overlapping contexts. It's potentially confusing so we try to avoid that. Fortunately, given a term with shadowing, we can always construct an alpha-equivalent term that has no shadowing. Except when studying variable binding itself, we only ever study terms up to alpha equivalence.

> Clearly $\Pi \alpha : \ast. \alpha \rightarrow \alpha =\_\alpha \Pi \beta : \ast. \beta \rightarrow \beta $ so I can change my problem to search for an alpha-equivalent term and now I can do it, but this feels like a hack.

It's not a hack, it's the normal thing to do. Systematically renaming variables (i.e. performing an alpha conversion) so that no shadowing occurs is called the (weak) Barendregt convention. In fact, the true Barendregt convention (from Barendregt's treatise on the lambda calculus) is a bit stronger: in a given term, you never use the same name for two different variables (even with non-overlapping contexts such as $(\lambda x. x)(\lambda x. x)$, which does not obey the strong Barendregt convention).

See also Free variables as defined in TAPL seems wrong and Substitution lemma for types.

---
Tags: lambda-calculus, type-theory
---


# Question
Title: How do i determine when I am at the left most character of a turing machine tape?
I am currently making a 2 tape turing machine for a language that has a binary palindrome (ex: L = {x is over {0,1} | x is a palindrome }. I can assume that the tape is only infinite in one way (the right side). and when using 2 tapes, the first one contains the input, the other is empty, and both heads start at the beginning of the tape.

So, my process has been:

1. transfer all of the letters from tape1 to tape2 (ex: 0,0,R | U,0,R would keep the symbol 0 on tape1 and move it to the right while changing the empty symbol on tape2 to 0 and moving it right as well).
2. Reverse tape1's head to the start again. However, I'm not sure how to do this if the tape is not infinite on both sides. I've been stumped on this part for a while and am unsure of how to continue.

# Answer
You can actually simply assume that the Turing Machine will not move passed the leftmost symbol on the tape if the tape is infinite only on the right. So, you can just say that it will move its head to the left until you reach leftmost cell of the tape. See for example, Sipser's description in Introduction to the Theory of Computation:

> *If $M$ ever tries to move its head to the left off the left-hand end of the tape, the head stays in the same place for that move, even though the transition function indicates L.*

Here $M$ is the Turing Machine and L indicates moving the head to the left.

In case you don't want this you can begin by shifting the contents of the tape one position to the right and put some kind of delimiter as the leftmost symbol. You can use a blank if in case you do not want to increase the number of tape symbols.
> 0 votes

---
Tags: turing-machines
---


title: Executable linking/loading workflow

text:
# Question
Title: Executable linking/loading workflow
I'm having a bad time understanding how multiple concepts work simultaneously for achieving linking/loading correctly an executable.

From the very beginning loading/linking is basically the art of putting another layer of abstraction over concrete memory addresses to achieve using the same piece of code over multiple executables (could be a shared lib linked to multiple binaries, an external library statically added in your code or even the same instance of a program under different memory assumptions like virtual memory|overlays and so on).

See Relocation wikipedia article, it explicitly states `Relocation is the process of assigning load addresses for position-dependent code` while Linkers & Loaders states `Relocation is the process of assigning load addresses to the various parts of the program, adjusting the code and data in the program to reflect the assigned addresses`. Question is my common sense says to me that relocation should not be tied to position dependent/independent code since always you need to attach concrete addresses to a program formed by multiple subprograms (let's say libraries), isn't it?. Also relocation is tied (as my current undestanding is) to linking while position independent(ness?) should be a loader concept since the idea is using a program regardless where the OS put it on RAM. Now second question is, how does position independent code works along virtual memory because for me seems like virtual memory solves the problem of loading stuff wherever you want (maybe not security issues though).

Let's keep going, while watching ASLR it shows Program possible load scenarios as a way to randomize how stuff is put on the RAM at runtime. Multiple questions arise from here

* The usual understanding of the heap/stack is broken, isn't the stack should be in decreasing order and the heap in increasing order (to avoid collisions between them)?. How is this handled now and how does it affect paging? (I imagine that a `random` layout would inevitable lead to ask pages to the OS quicker than the old classical layout, maybe I'm wrong)
* This seems to need another relocation step(s?) here in order to fulfill loading a program which previously was statically understood (talking about layout without counting shared stuff) but in the fly was loaded totally different. How does this relates to position independent code?

There is a great resource on virtual memory, see Architecture and operating system support for virtual memory, but I might be not fully understanding how this play around with linking/loading (and the concepts above PIC/ASLR) in the big picture on a per process basis. I need help here because I'm a little bit lost (just began with malware analysis stuff that's why I'm interested in this low level stuff), if someone is able to help would be really appreciated.

# Answer
> 1 votes
There's a huge number of questions here, so I'm going to go through what I think the central question is, and try to come up with a reasonably self-contained answer that, I hope, addresses what you wanted to know.

Here's the important point: Executable files are typically loaded at a known virtual address, but DSOs (dynamic shared objects, think `.dll` on Windows or `.so` on Unix) are typically not.

The clue is in the word "shared"; the same DSO can be shared between multiple running programs. Moreover, you cannot statically assign load addresses to all DSOs without knowing which executables will load which DSOs in advance. Application plugins are the obvious case in point.

Thanks to the virtual memory system, the same DSO may be loaded at different virtual addresses in different running programs, and the physical memory for any static information (e.g. program text) will be shared between them. And thanks to large 64-bit address spaces and ASLR (address space layout randomisation), they usually *are* loaded at different virtual addresses.

This means that at link time, an executable can have all of its global names resolved to a known virtual address, but a DSO cannot.

There are two interesting cases: references from *code*, and references from *static data*.

For references that are entirely within a DSO (i.e. referencing a global name within the DSO from within the same DSO) in code, you can usually write position-independent code on most modern CPUs, but how exactly this is achieved depends on the kind of reference, the ABI, and the architecture.

Just as an example of that last point, 32-bit Intel-esque CPUs have a PC-relative call instruction, but no PC-relative load/store instruction, so while calling functions within the DSO can be resolved at link time, loading and storing static data cannot. Different ABIs handle this in different ways, such as reserving a register to point to an appropriate location in the data segment, or using the Apple solution of loading the instruction pointer into a user register only if needed:

```
        call label
label:  pop %ebx
        // Register %ebx now holds the address of "label", and
        // can be used as a base for subsequent memory accesses.

```

X64 does have IP-relative addressing, so hacks like this are not needed.

So that takes care of code, but you still need to think about static data, which can introduce the need for load-time relocation even when there are no obvious instances of "take the address of this symbol" in the source code.

```
/* How many times have you written code like this? */
const char* static_strings[] = { "Hello", "world" };

```

Given that modern operating systems need to support running arbitrary code when a DSO is loaded (e.g. static initialisers in C++), load-time relocation is typically offloaded onto the DSO itself these days, with the "loader" proper just handling cross-object name resolution.

Stacks and heaps are a whole other topic, and I think that would be worth a separate (and specific!) question. I will merely note that multi-threading already complicates the picture that I think you may have in your head.

# Answer
> 1 votes
Virtual memory is transparent to your questioning. Every execution unit (process) sees the whole virtual space as flat and is unaware of the actual underlying storage in different memory levels.

A linker can perform static relocation, i.e. assign the addresses that must be used by the loader. It organizes the global mapping of all data and compiled code.

PIC code can still be relocated by the loader, as all internal address references are relative to a base register.

---
Tags: operating-systems, compilers, virtual-memory
---


# Question
Title: I Don't Understand Nothing About Operating Systems even After reading books
I'm a programmer, let's start by that. The question may sound really broad, and in fact it is. I'll list some things that I know, and some other things I've doubts about under the form of questions.

My current understanding is the following:

You have a CPU. This CPU can have multiple cores. Each core runs in parallel. Ok. This implies that at any given time t, we have different core states for all cores. I also know about the booting of a general computer. Looking for operating systems on the non-volatile memory and mapping it onto ram. Then you have RAM filled only with kernel code. These things are just instructions CPU is executing to get everything set up.

I have a question that just popped in my mind right now:

At this stage for example, do we only have one core executing these set-up instructions?

Anyhow continuing this discussion, now that the operating is in memory, cpu gives it control. Meaning up to the point where the OS wasn't loaded, CPU alone had no idea of what a process even is, is it only conceptualized by the operating system? Does the operating system has an actual C-like STRUCT for processes to conceptualize them? Or modern CPUs are somehow built so that the concept of a process coexists even without referring to OS?

Operating System is just a software, often called kernel, so it has actual executable code. Fine. This means that the CPU will execute it. But When? We also have processes which are user-written programs, executed as well. How does the operating system even keep track of these processes? Like come on there has to be some code executing somewhere right? I know operating systems have source codes, so they are actually concrete software running. What is the relationship between Operating System and the CPU? How are processes even executing in parallel? I've read about scheduling, but concretely speaking what is that? Is it an actual piece of code that's being executed on the kernel space at times DECIDED by the cpu and not by the operating system? Because if a user-written process is executing, then in no way the operating system can actually stop its execution, unless there is some internal hardware mechanism that actually stop executions of processes and then gives the operating system the privilege to run to decide what to do next. I have really no idea of how it all works.

As you may see my brain has a lot of concepts but they are all hanging and I know deep inside my soul they are all interconnected, but for some reason I AM NOT seeing this link. It all seems too abstract.

What I'm hoping for is either a mind-refresher comment to tie these things all together inside my brain, or suggestion of a good textbook that in a very PRACTICAL way talks about operating systems and hardware, most of them that I found aren't very practical or at least I don't have the patience to learn things starting from abstract explanations.

# Answer
First off: an OS is nothing magical. It's code like yours or mine. I've written one (a small one), you can too. Waste of time though, since Linux already exists and it does more than you or I could write.

You have a CPU. It runs instructions. It doesn't know about processes. It doesn't even know about functions. Or lines of code. Or the screen. It just does one instruction after another, forever.

Cores are CPUs. You think have a 4-core CPU, you actually have 4 CPUs in one chip.

---

**Booting**

The CPU is hard-wired so it starts by running code from the BIOS chip on your motherboard and that chip is hard-wired so the CPU can directly run code from it without loading. Well, one of them is. The other 3 are hard-wired to do nothing. That's how you can still run MS-DOS (maybe) and waste 3/4 of the CPUs you paid for.

The BIOS code looks at all your hard drives, your CD drive, your USB ports, finds a signature that says "hey this drive has an OS on it", loads that and jumps to the address it just loaded. The old-school MBR system is just the first 512 bytes of any drive, ending with hex codes 55 AA to say that it's bootable. Since it's only 510 bytes you normally put here a program that loads more bytes. The more modern ~~Chat~~GPT system is more complex and the BIOS loads all the bytes you want, not just the first 510. No point going into detail here.

With either MBR or GPT, once the BIOS loads these bytes and then jumps to their address, the computer is all yours to do as you wish. Usually what it just loaded is another loader which loads the operating system, but that's a historical accident, not something necessary. (Well, it's necessary in MBR if your operating system is more than 510 bytes big, which is the historical accident)

You have 1 CPU running whatever code you like, and 3 CPUs still asleep. For the time being, let's see what you can do with just 1 CPU.

What code do you like? It can be anything. Use your imagination. But let's say you want to make something like Linux but more basic. Linux has a whole lot of parts. You asked about one specifically. You asked about the scheduling.

---

**Scheduling**

There's a little magic trick to scheduling that makes it all understandable. The magic trick is that CPUs are extremely forgetful. See, the CPU contains a bunch of registers - which is to say very small memory circuits, the hardware equivalent of variables - different ones depending on which kind of CPU you have, but on x86 you have registers like eax, ecx, edx, ebx (yeah the order is ACDB, don't ask what Intel were smoking), esp, eip, cs, ds, es, and a bunch more. Some of them are general-purpose; some have very specific purposes. And those are the *only things* the CPU can remember. No, it can't remember the current process ID. No, it can't remember what it was doing 2 instructions ago. No, it can't remember whether it's been running this loop for 50000 iterations or whether the loop counter started at 50000. It's Last Thursdayism on a microscopic scale.

So if you want to swap threads all you have to do is save all the data in the registers into memory (you could call that place `struct thread`) and load them from somewhere else in memory (a different `struct thread`) back into the registers. Now the CPU continues running the second thread just as if it had been doing it all along. This is called a **context switch**. In fact, you can already do this in your own program without OS help - on Linux there's a supported library function called `swapcontext`.

Keeping track of which thread is currently running is your problem, not the CPU's.

But how does it happen without the thread calling `swapcontext`? Enter: **interrupts**. One of the ways that hardware talks to the CPU is by signalling an "interrupt request" which tells the CPU to stop what it's doing and run some OS code - it makes the CPU do an automatic context switch.

The details vary depending on the CPU type. x86 CPUs have quite complicated interrupts, so let's talk about ARM which is much simpler. When an ARM CPU is running some code ("user code") and gets an interrupt request, it only does a few simple steps:

1. it notes the current instruction address (in ARM terms that's `PC` or `R15`)
2. it activates the "interrupt mode" bit in the CPU status register
3. it stores the current instruction address in register `R14_irq` which is only used in interrupt mode
4. it jumps to the instruction at address `0x00000018` (which is hard-wired)

Of course, there's also a `r`eturn `f`rom `i`nterrupt instruction which does the opposite. Of course, the operating system will have made sure that address 0x00000018 has OS code, so the operating system now has control of the CPU and can run whatever code it likes.

Clearly it's not a full context switch. Only the current instruction address is saved and updated. But that's enough for the OS code to do the rest of it. It isn't possible to context switch the register R14\_irq properly, because the old value in that register got overwritten. Nobody notices, though, because user code can't touch that register, and OS code deliberately doesn't touch it except when it's processing an interrupt.

One hardware device that creates interrupts is a *timer*, like an alarm clock. The OS sets the alarm clock before it starts running code from a process. When the alarm clock rings, it makes an interrupt and then the CPU is running OS code once again, even if the process got into an infinite loop.

An OS can run multiple processes on one CPU by cycling through them and setting short alarms (few milliseconds, or less). Of course, the OS also knows which processes don't want to run (which is most of them, most of the time) and skips over those.

Other than timers, interrupts are also used for all sorts of hardware, especially inputs like mice and keyboards so that the OS can do something immediately when you press a key.

---

**Multiple processors**. What about the other 3 CPUs? Actually that one's easy - you use the main CPU to send them some specific signal (just like you send signals to disk drives or keyboards) that tells them to turn on and what code address to start from.
> 2 votes

---
Tags: operating-systems, cpu
---


# Question
Title: Check if these 2 regular expressions are equivalent
**Check if these 2 regular expressions are equivalent:**

$R\_1 = (a+b)^\*(aa+bb)$

$R\_2 = (a+b)^\*aa+a^\*bb+b^+b$

**My approach:**

We check if both of these expressions generate the same set of strings. Meaning that any string that can be generated by $R\_1$ can also be generated by $R\_2$, and vice versa.

$R\_1$ can generate strings starting with empty string, or one or more occurrences of $a$ or $b$ and ending with either $aa$ or $bb$.

The start of the word $(a+b)^\*$ generated by $R\_1$ can also be generated by $R\_2$ with $(a+b)^\*$, so we can break down the cases based on the ending of the $R\_1$ strings:

1. $R\_1$ ends with $aa$ – can be generated by $R\_2 = (a+b)^\*aa$
2. $R\_1$ ends with $bb$ – can be generated by $R\_2 = (a+b)b^+b$ (where $b^+=b$)

Thus $R\_1 ⊆ R\_2$.

No we check it for the other way. Again the start of the word $(a+b)^\*$ generated by $R\_2$ can also be generated by $R\_1$ with $(a+b)^\*$, so we can break down the cases based on the ending of the $R\_2$ strings:

1. $R\_2$ ends with $aa$ – can be generated by $R\_1 = (a+b)^\*(aa)$
2. $R\_2$ ends with $a^\*bb$ – can be generated by $R\_1 = (a+b)^\*(bb)$, because $(a+b)^\*a^\* = (a+b)^\*$
3. $R\_2$ ends with $b^+b$ – can be generated by $R\_1 = (a+b)^\*(bb)$, because $b^+b = b^\*bb$ and again $(a+b)^\*b^\* = (a+b)^\*$

Thus $R\_2 ⊆ R\_1$.

We get that $R\_1$ and $R\_2$ are equivalent.

Is this approach correct for this case? I know that for more complex expressions it would be easier to compares the corresponding DFA's.

# Answer
Yes, the approach is correct, but there are some mistakes:

1. Statements such as

* $R\_1$ ends with $aa$ – can be generated by $R\_2 = (a+b)^\*aa$

are a bit sloppy. What you mean to say is:

* $R\_2$ is the union of 3 expressions, $R\_{2,1}, R\_{2,2}, R\_{2,3}$
    * $R\_1$ can be written as the union of 2 expressions, $R\_{1,1}$ and $R\_{1,2}$
    * hence, to prove equality, it suffices to show that $\forall x \exists y: L(R\_{1,x}) \subseteq L(R\_{2,y})$, and vice versa (5 statements in all)
    * and then you proceed to prove those 5 statements
2. One of those 5 statements is incorrect, and there is a mistake in the proof.
> 1 votes

---
Tags: regular-languages, regular-expressions
---


title: Equivalence of LR(k) and LL(k′) parsers

text:
# Question
Title: Equivalence of LR(k) and LL(k′) parsers
Are there languages that can be parsed by an LR(k) parser but not by an LL(k′) parser for any k′?

# Answer
> 2 votes
Yes, $\\{a^i b^j c \mid i \ge j \ge 0\\}$ can be parsed by a $LR(0)$ parser but not by any $LL(k')$ parser for any $k'$. See How does $LL(n)$ languages compare with $LR(0)$, for $n\>0$?.

See also https://stackoverflow.com/q/36652221/781723 and Language theoretic comparison of LL and LR grammars.

---
Tags: formal-languages, formal-grammars, parsers, lr-k
---


# Question
Title: Optimal worse-case sorting algorithm when some comparisons are cheap
I want to sort a set of items, where some comparisons are expensive and others are cheap. What is an algorithm that will minimize the worse-case number of expensive comparisons?

For instance, I want to rank sports players (assuming performance is completely deterministic, i.e. a game between two players will always have the same result), where some comparisons are already known, but others will require the players to play a game.

More formally, my machine has access to two oracles $f(a, b) \in \\{\<,=,\>,\mathrm{unknown}\\}$ and $g(a, b) \in \\{\<,=,\>\\}$, and I want to sort my list of items with the smallest worse-case number of calls to $g$ (which of course depends on the specific cases for which $f$ returns "unknown").

One approach I thought of is to extend $f$ into $f'$, which removes the unknown results that can be determined by transitivity, then use a standard sorting algorithm, calling $f'$ first, then $g$ if $f'$ returns "unknown". I'm not sure whether this is optimal (it may depend on the specific sorting algorithm).

I'd be satisfied with an algorithm that is near-optimal. I have about 100 items.

# Answer
> 2 votes
Your problem amounts to finding a linear extension of a given partial order, using the minimum number of comparisons between two elements. @Tassle highlights the following paper, which I believe is the state-of-the-art:

Sorting under Partial Information (without the Ellipsoid Algorithm). Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël Jungers, J. Ian Munro. Combinatorica 33, 6 (2013), 655–697.

I have seen some papers call this the "SUPI" problem (Sorting Under Partial Information).

However, this algorithm is fairly complicated. If you want to a practical heuristic, that comes with no guarantees, you could try using a greedy heuristic.

Define some metric that represents how much uncertainty their remains about the final order, and that can be computed efficiently. For example, perhaps you can count the number of pairs whose order remains unclear (i.e., they are incomparable in the transitive closure). Then apply the following algorithm:

1. Compute the value of the metric on the current partial order.
2. For each pair $(x,y)$ you could possibly query next:

* Compute the value of the metric if this query returns $x\<y$, and the value if it returns $x\>y$, and average those two metrics (or better yet, compute the max of these two metrics).
3. Pick the pair $(x,y)$ that reduces this metric the most. Query this pair $(x,y)$.
4. Update the current partial order with the result of this query (and apply the transitive closure). Go back to step 1 and repeat, until you have obtained a total order.

I don't know how well this will perform in practice, but it would be simple to implement and you could try it out.

The ideal metric would be the entropy, i.e., the log of the number of linear extensions compatible with the current partial order, but unfortunately it is #P-hard to compute that metric, and approximating it takes you deep into complicated algorithms, which I suspect you might want to avoid.

---
Tags: sorting
---


# Question
Title: Algorithms for sorting under some restrictions
I was recently sorting a large list of names - I just ended up sorting it in Python, but it inspired in me the following question. If we're given a list $L$ of $n$ numbers, but can only see $k$ contiguous elements at a time and can shift a group of elements at once, what would be the fastest way to sort this list?

I originally had the list of names in Notepad. You can only see up to the number of rows at once, but you can cut and paste a bunch of rows at once. What I started to do is organize it into bunches of runs, but then you run into the problem of having two runs that are separated by a long gap (like as in the final step of merge sort, the two halves are separated by a large gap).

Let's say for concreteness that in this problem, there are three operations available to you given a view of the list $L\[i+1\]$ to $L\[i+k\]$: "cutting" from $m$ to $m+j$ with $i+1\le m$ and $m+j\le i+k$ (i.e. removing that range from the list, and storing that range in memory), changing the view to see some different group of $k$ (which takes time linearly proportional to the change in the view), and "pasting"/inserting all of memory to a location in the current view. Also, a cut operation can't be followed by another cut operation without first pasting it, and the only memory available is what you have in the "clipboard" (and maybe some constant size of memory not dependent on $k$ or $n$ \- EDIT: this could be $O(\log n)$ additional memory instead, since otherwise, you couldn't store indices). Let's also say that comparisons take no time.

I don't think we can reach the $O(n\log n)$ efficiency of sorting algorithms like merge sort and quicksort in general, especially when $k$ is small in comparison to $n$ because you're limited in the amount you see at once. For example, if $k=1$, then I think the best you can do is something like insertion sort or selection sort for an $O(n^2)$ efficiency. But if $k\>n$, then you can just do a normal merge sort or quicksort for $O(n\log n)$ efficiency.

What would the runtime be in the general case with an optimal algorithm (and what would the optimal algorithm be)? I'm mainly interested in asymptotic running time, rather than practical approaches, although those are of interest too.

Also, if there's anything vague in the question, or something that seems different to what I may have intended, please let me know.

# Answer
> 1 votes
With $k=1$ you can solve this in $O(n \log n)$ time using sorting networks.

Pick a sorting network of size $O(n \log n)$. You can implement each comparator using $O(1)$ steps, in your model. (To compare-and-sort the items at indices $i,j$, first cut the item at $i$ into memory, then move the window to $j$, then insert $i$ at the appropriate location before or after the item at $j$, then cut the other item and move it to $j$. This requires only $O(1)$ space, to store the indices $i,j$.) It follows that you can implement the sorting network in $O(n \log n)$ steps in your model, which in turn suffices to sort.

This is completely impractical, as the constant factors hidden in the big-O notation are enormous. A more practical algorithm would be to use bitonic mergesort or the pairwise sorting network, whose asymptotic time is $O(n \log^2 n)$, but whose constant factors are much more reasonable.

---

As Yves Daoust explains, "Your model does not account for the time to scroll the window. IMO this can be the dominant cost." This means that my answer is totally useless for the Notepad scrolling issue you actually ran into, because we must account for the time to scroll. That is treated above as taking $O(1)$ time regardless of how far you scroll, which is not realistic in practice.

---
Tags: algorithms, time-complexity, sorting, efficiency
---


# Question
Title: Example of L not regular language that suff(L) is regular
I can't find example of L not regular language that suff(L) is regular I tried something like this: {0^n1^n|n\>= 0}, but i can't prove that it's suffix is regular

Suff(L) = {x ∈ Σ ∗ | ∃u ∈ Σ ∗ such that u · x ∈ L}.  thank you for the help :)

# Answer
> 2 votes
Let $L = \\{ 0^n \mid n \text{ is prime}\\}$. Suppose towards a contradiction that $L$ is regular and let $p$ be a prime not smaller than the pumping length of $L$. The pumping lemma ensures that there is some $k$ such that $1 \le k \le p$ and $0^{p+ki} \in L$ for all $i \ge 0$. Choosing $i=p$ we have that $p+kp = p(k+1)$, which is not prime. We conclude that $L$ is not regular.

To show that $\textsf{Suff}(L)$ is regular, let $w = 0^{|w|}$ be any word in $\\{0\\}^\*$. Since there is a prime $p \ge |w|$, we have that $0^{p-|w|} 0^{|w|} \in L$, therefore $w \in \textsf{Suff}(L)$. Then, $\\{0\\}^\* \subseteq \textsf{Suff}(L) \subseteq \\{0\\}^\*$, i.e., $\textsf{Suff}(L) = \\{0\\}^\*$, which is clearly regular.

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


# Question
Title: Are quantum computer strictly "faster" than any massively parallel computer in terms of computational complexity?
I've seen that quantum computing calculations have their own complexity classes https://en.wikipedia.org/wiki/Quantum\_complexity\_theory, namely BQP and QMA.

I've heard that this would beat any classical computer, but I wonder if it would also beat a custom-made *massively parallel computer*. By massively parallel computer I imagine a huge number of little *mini-computers* each with a tiny memory and all of them *arranged in 3-dimensional space*. Each mini-computer can *communicate with its local neighbors*. During one step each mini-computer performs some internal computation and then sends information to its neighbors. I suppose this massively parallel setup allows for faster computation that a classical computer?

How would one define an appropriate complexity class for such a massively parallel setup? I suppose one needs to limit the number of mini-computers used? Is there an existing computation class for that?

Are the quantum complexity classes faster than this massively parallel class (for large problem instances)?

By "faster" I generally mean faster for *some* problem and a sufficiently large problem size. I know that quantum computers are always probabilistic, so for comparison it's ok if the parallel computers implement a probabilistic method, too. In terms of resources (qubits, mini-computers) their scaling should be comparable (otherwise one method would outperform the other due to limitation of resources).

For the physics-minded people: If the quantum complexity class is faster than the massively parallel class, does that mean that quantum computers cannot be described by a conventional field theory? In a field theory each position in space has some information - essentially my mini-computers. During each time step there are simple local rules (a differential equation) according to which the information at each position evolves. This is the next-neighbor-communication of my mini-computers.

In the end, I'm looking for a rigorous answer to the question: If quantum mechanics were described by some differential equation (a field theory, essentially the massively parallel mini-computers), then quantum computing would be impossible, because quantum computing promises to be faster than any massively parallel classical computer?

# Answer
Nope. For some problems, quantum computing is far more powerful than parallelization. If quantum computing can be made to work in practice and can scale (which is not yet known yet), then no, a massively parallel computer cannot do everything that a quantum computer can do.

Intuitively, the reason is that for some problems, quantum computing gives us an exponential boost over non-quantum algorithms. You can't make up for that exponential with parallelization, once problem sizes get large: the exponential turns into a really large number.

For instance, consider the problem of factoring large integers. Shor's algorithm allows to factor integers in polynomial time (approximately quadratic time in the size of the integer). The best non-quantum algorithms we know take sub-exponential time (approximately exponential in the cube-root of the size of the integer). The latter grows far faster than the former. So, if the integers are large enough, the gap between these two running times is tremendous and cannot be made up with a parallel computer.

For instance, suppose we want to factor a 100,000 bit number (that is a product of two large primes). Then the best non-quantum algorithms that are known are expected to take more than $2^{361}$ steps of computation (probably a lot more than that, actually). Now if you somehow managed to program every atom in the known universe, so that each atom is its own separate mini-computer, executing $10^9$ steps per second, and you ran this parallel computer (which takes up the entire universe) for the lifetime of the known universe, then that still would not be long enough to factor such a number. So no real classical algorithm could ever hope to factor such a number, no matter how much parallelization you use.

However, if quantum computing can be made to work in practice and if it scales, then in principle, we should be able to factor such a number. It might be difficult, but it is just a matter of engineering -- there is no fundamental limit preventing that.

---

This assumes you are interested in the amount of resources needed to compute something. If you don't care about the amount of resources, and just what can be computed in theory given unlimited resources, then there is no difference between quantum vs classical algorithms. Anything that can be computed by a quantum algorithm can be computed by a classical algorithm -- possibly with an exponential slowdown, or with exponentially more resources (e.g., exponential parallelization). In particular, there are classical algorithms for simulating the evolution of any quantum system. They're just incredibly slow for complex systems. If that is your perspective, you don't even need a parallel computer -- it suffices to use a sequential algorithm and let it run exponentially long.
> 1 votes

---
Tags: parallel-computing, quantum-computing
---


# Question
Title: Can the optimization version of a problem be NP-hard while its decision version is in P?
I have formulated an instance of a 0-1 Integer Program (IP), which I am trying to determine the complexity of (can this instance be solved in polynomial time or not). As we know, the 0-1 IP is NP-complete, but I suspect my instance can be solved in polynomial time; which of course does not contradict the hardness of the general 0-1 IP.

Given are a set of variables $S = \\{s\_0, \dots, s\_n\\}$, a set of values $V = \\{v\_0, \dots, v\_m\\}$, a set of costs $C = \\{c\_0, \dots, c\_m\\}$ (where each $v\_j, c\_j \in \mathbb{Z^+}$), and a positive integer $K$. Assume the values in $V$ and costs in $C$ are sorted, so that the last value in $V$ is the highest, and has the highest corresponding cost.

The optimization version of this problem asks which assignment of $v\_j$ to $s\_i$ has the lowest cost, where the sum is at least $K$? In addition, each $s \in S$ can only hold one $v \in V$.

To formulate this as a 0-1 IP, we construct a set of binary decision variables. Let this set be $X=\\{x\_{00},x\_{01}, \dots, x\_{0m}, \dots, x\_{nm}\\}$, where $x\_k \in \\{0, 1\\}$ denotes if $v\_j$ has been assigned to $s\_i$. We then get the constraints:

$$\sum\_{j=0}^{m}x\_{ij} \leq 1 \quad \forall i=0,1,\dots,n$$ where the last constraint makes sure the sum is at least $K$: $$\sum\_{j=0}^{m}x\_{ij}v\_j \geq K \quad \forall i=0,1,\dots,n$$ The 0-1 IP can then be formulated in its canonical form as: \begin{align} &\text{min} & & c^Tx \\ &\text{s.t} & & Ax \leq b \\ & & & x \geq 0 \end{align} Note that in this represntation, $C$ and $X$ are denoted $c$ and $x$ as they are vectors.

The decision version of this problem asks wether there exists a solution which satisfies $Ax \leq b$. This can be done in polynomial time by setting $x\_{im} = 1 \quad \forall i = 0,1,\dots, n$, i.e., every $s \in S$ is assigned the highest value. If the sum of these values are at least $K$, then the answer is "yes", i.e., there is a solution which satisfies $Ax \leq b$. If "no", then there is no solution, because the highest possible sum has been tested.

My question: Since the decision problem can be solved in polynomial time, does it imply that the optimization problem also can be solved in polynomial time? For instance, if the size of $S$ is large, there may be trillions of solutions that satisfy $Ax \leq b$. My knowledge regarding how optimization algorithms work is limited, but as far as I understand, the solution space is 'fixed', so an algorithm would 'only' have to compare the solutions against each other to find the optimal one.

Lastly, I did not use the set $C$ in my decision question. Therefore I am not 100% certain that it is the 'correct' formulation.

I have also read the follwing stackexchange posts:

# Answer
> Lastly, I did not use the set $$ in my decision question. Therefore I am not 100% certain that it is the 'correct' formulation.

It is not correct, indeed :)

You are describing a decision problem, but it does not correspond to your optimization problem. One of the questions you posted (Optimization version of decision problems) explains that quite nicely. Quoting the shortest path example from there:

> optimization/search version: Given an undirected unweighted graph $=(,)$ and two vertices $,∈$ , find a shortest path between $$ and $$ .

> decision version: Given an undirected unweighted graph $=(,)$ , two vertices $,∈$ , and a non-negative integer $$ , is there a path in $$ between $$ and $$ **whose length is at most**

The emphasized part is what you are missing. The corresponding decision problem is *not* about finding *any* solution for the optimization problem. Instead, it is about finding a solution that is at *least* as good as $$ for some constant $$.

So, in your example, you should replace this sentence

> The decision version of this problem asks wether there exists a solution which satisfies $≤$ .

with this

> The decision version of this problem asks wether there exists a solution which satisfies $^≤k$ (and, of course, still satisfies $≤$) .

to get the correct corresponding decision problem.

Now, if the decision problem is in $P$, you can invoke its polynomial algorithm several times for increasing $k$ and in a binary search manner you will find the answer for the corresponding optimization problem. So, you solved that in polynomial time, too.
> 2 votes

# Answer
Often, if the decision problem can be solved in polynomial time, the optimization problem can be solved in polynomial time as well. For example, if you could decide in polynomial time if a problem has a solution with at most a certain cost, you may be able to binary search for the minimal possible cost.

Your decision problem, however, does not have any restrictions on the cost, and can therefore not be exploited to solve the optimization problem in polynomial time. (In fact, your optimization problem is NP-hard as it can be reduced from the unbounded knapsack problem.)
> 2 votes

---
Tags: complexity-theory, optimization, np-complete, integer-programming
---


# Question
Title: How PDA decide when and which state to transform to?
\[1\] gives an example for PDA which contains rules of:

```
(p,e,Z,q,Z)
(p,e,A,q,A)

```

and says,

> The third and fourth instructions say that, at any moment the automaton may move from state p to state q.

So, how does PDA know when it needs to move from a state to another?

\[1\] https://en.m.wikipedia.org/wiki/Pushdown\_automaton

# Answer
> 2 votes
Quoting the same Wikipedia page (emphasis mine):

> If, in every situation, at most one such transition action is possible, then the automaton is called a deterministic pushdown automaton (DPDA). In general, **if several actions are possible**, then the automaton is called a general, or **nondeterministic**, PDA. A given input string may drive a nondeterministic pushdown automaton to one of several configuration sequences; if **one of them** leads to an accepting configuration after reading the complete input string, the latter is said to belong to the language accepted by the automaton.

A concept of determinism is applied to multiple structures in Computer Science, e.g. automata and Turing machines. In general, an automaton is called deterministic when there is exactly one transition from every state. All actions are *determined*, there is a single computation path, and the automaton either accepts the string or does not.

In contrary, nondeterministic automata may have several distinct transitions from some states. Each transition gives a different computation path, so the path is not determined by the input anymore but there may be multiple paths corresponding to a certain input. There are several ways to define the language with regard to nondeterministic automata, but the most common one is to require having at least one accepting path. (The other way may be to require *all* paths to lead to accepting state, not a single one, thus replacing $\exists$ with $\forall$; it may be convenient in defining complexity classes like co-NP.)

You may interpret it as guessing: whenever you meet a state with multiple transitions, you make a guess and pick an arbitrary one. The word is accepted if it is possible to make correct guesses and arrive to the accepting state.

---
Tags: pushdown-automata
---


# Question
Title: How is there a paradox in the halting problem when you can trace it and it's very clearly non-halting?
Here's Alan Turing's halting problem in pseudocode:

```
function halts(f: Function, input: any): boolean {
  // Some logic that can supposedly solve the halting problem
  // ...
}

// A function that takes itself as an argument and does the opposite of what halts says
function paradox(f: Function, input: any) {
  if (halts(f, input)) {
    while (true) {}
  } else {
    return;
  }
}

halts(paradox, paradox); // returns false

```

In line 1 of `paradox`, we have to detether or not `paradox` is halting. However, `halts` will also recognize that we're attempting to call `paradox` with `paradox` as a parameter, therefore invoking infinite recursion, therefore `paradox` is non-halting.

Where's the problem?

# Answer
> 3 votes
> However, `halts` will also recognize that we're attempting to call paradox with paradox as a parameter, therefore invoking infinite recursion

You seem to have a particular implementation of `halts` in mind. Also, your reasoning is not correct even assuming that implementation.

Remember that the proof works for *any* possible implementation, it doesn't matter what the actual implementation is.

As for where your reasoning is incorrect, you seem to think that if `halts` can check for a function calling itself, then that means it will detect an infinite loop. This is not the case. There are many functions that do not infinite loop when calling themselves; for example

```
function foo(x):
    if x == foo:
        print "Called foo on input foo!"
    return

```

Additionally, `halts` cannot just look into the implementation to see whether `paradox(paradox)` infinite loops, because if it does so, it will find that the infinite loop `while (true)` is *guarded* by a call to `halts(paradox, paradox)`. So, there is no trivial implementation of halts that works here. Indeed, the whole point of Turing's proof is to show that no such implementation of `halts` exists.

---

P.S.: You have a typo in your pseudocode. The paradoxical function should only take one argument and call it on itself:

```
function paradox(f: Function) {
  if (halts(f, f)) {
    while (true) {}
  } else {
    return;
  }
}

```

---
Tags: recursion, halting-problem
---


# Question
Title: Do all P problems reduce to all NPI problems?
It is often said that NP-intermediate problems, such as factoring, graph isomorphism, discrete log, and so on are "harder" than the problems in P. Meaning that they cannot be solved in polynomial time.

But does this imply that all problems in P reduce to all problems in NPI?

This would imply that all problems in P reduce to all problems in NP, because $NP = P \\: \cup NPI \\: \cup \texttt{NP-complete}$. All problems in P are equivalent (besides the empty and full languages) and all problems in NP reduce to NP-complete problems. So if all problems in P reduce to NPI problems, all problems in P reduce to all NP problems. This doesn't really seem right though.

# Answer
If your notion of reduction is polytime m-reduction, then all problems in P (except the empty and full problems) reduce to all problems *whatsoever*, not just the ones in NP. In particular, any two problems in P are reducible to each other (modulo the previous parenthetical).

Note that I was explicit about the choice of reducibility above. There are of course reducibilities which do distinguish between problems in P (e.g. logtime m-reducibility). However, every notion of reducibility will have its own kind of "minimal complexity" class of problems. Problems in this class will be reducible - in the appropriate sense - to all other problems.

(Very minor terminological annoyance: in computability theory, the term "minimal degree" is used to refer to degrees - i.e. equivalence classes of languages with respect to some appropriate reducibility - which are *nonzero* and *not strictly above any other* nonzero degree in the sense of that reducibility. As far as I know this usage doesn't occur in complexity theory, but it's worth warning about.)
> 2 votes

---
Tags: np, polynomial-time, np-intermediate
---


# Question
Title: Measuring time complexity in the length of the input v/s in the magnitude of the input
I know that formally the time compliexity of an algorithm is measured in the length of the input, which in binary would be the number of bits required to encode the input.

The problem that I have with this definition is that wouldn't this definition make a lot of seemingly obvious poly-time algorithms involving numbers exponential time?

For example, consider the algorithm of listing all integers between 1 and another integer n. The algorithm would be a simple loop, listing a number in each iteration from 1 to n. This loop would have $n$ iterations and would thus take $O(n)$ time.

Now if $n$ is encoded in $b$ bits then $b = \lg n \implies 2^b = n \implies$ in the length of the input the algorithm is $O(2^b)$ which is exponential, which is very unintuitive because the loop, in each iteration, does constant amount of work and there are $n$ iterations in total.

By the same logic, consider a loop that prints Hello World $n$ times, where $n$ is an integer, then by the same procedure as above, this algorithm would also be exponential time in the length of the input $n$.

What am I missing?

# Answer
You're not missing anything -- you are correct!

> Consider a loop that prints Hello World $n$ times, where $n$ is an integer, then by the same procedure as above, this algorithm would also be exponential time in the length of the input $n$.

Correct. This *is* an exponential time algorithm.

If it helps, remember that in most programming languages, integers are represented in binary. If the integer is $32$-bits long, that means the loop might run up to $2^{32} = 4294967296$ times! That's a rather long time. If I use 64-bit integers or big integers, the running time could be far worse.

> Now if $n$ is encoded in $b$ bits then $b = \lg n \implies 2^b = n \implies$ in the length of the input the algorithm is $O(2^b)$ which is exponential, which is very unintuitive because the loop, in each iteration, does constant amount of work and there are $n$ iterations in total.

What you're getting at here is that it's important to distinguish your variables when using big-oh notation. Whenever I say "linear time" or "exponential time", really we should be more precise: linear **in what variable?** Exponential **in what variable?** In your case, the algorithm is exponential **in $b$**, but linear **in $n$**. That is, the algorithm is:

* Exponential in the size of the input
* Linear in the value of the input

and both of these statements are simultaneously true!

When we don't specify the variable, we usually mean in the size of the input, so we would use the first statement. But the second statement is also sometimes useful. For example, if this loop is embedded in a larger program where $n$ is the length of a list $L$, then the loop would be linear in the size of the input (i.e., linear in the size of $L$).

---

**Edit:** Why is this useful?

The short answer is because "length of the input" is the most general way to describe complexity that isn't specific to a particular type. For example, if we have a sorting algorithm on lists, $f: \text{List} \to \text{List}$, it wouldn't make sense to say $f$ is linear (or quadratic or exponential) in the *value* of its argument. So by default, we always use the *length* of the input to describe complexity in a generic way.

Additionally, it turns out that this type of complexity is more compositional. Using the length of the input as the parameter, we can prove, for instance, that the composition of two linear algorithms is linear, and that the composition of two polynomial algorithms is polynomial.

However, you're free to describe algorithms on integers in terms of the value of the input -- there's nothing wrong with that! You just have to be clear to specify so that there's no confusion.
> 20 votes

# Answer
@CalebStanford's answer is excellent, but just to add one point:

There is a distinction between how many *operations* are needed and how many *bits* are needed (more for each number of many digits), and the latter introduces an extra $O(\log n)$ factor because$$\sum\_{i=1}^bi2^{i-1}\sim b2^b\sim n\log\_2n$$for $2^{n-1}\le b\le2^n-1$. This $O(n\log n)$ behaviour is a *linearithmic* bit complexity, even though the operation complexity is linear in $n$. Both are exponential in $b$ because$$n\log n\sim b2^b=2^{b+\log\_2b}\in o(3^b)\setminus O(2^b).$$ But in terms of $n$, where the $\log n$ factor affects classification, which complexity measure does one call "time complexity"? As explained here, at least one version of the sieve of Eratosthenes for finding primes up to $n$ needs $O(n\log\log n)$ operations but has bit complexity $O(n\log n\log\log n)$. They prefer to apply the term "time complexity" to the former.

Depending on the context, this distinction can be more important, not to mention warranting fussier questions about how you count operations. Famously, bit complexity must be at least big-O of space complexity, but operation complexity might not be. For example, how quickly can you compute the $n$th Fibonacci number? There's  technique that takes $O(\log n)$ matrix multiplication operations, but $F\_n$ has $O(n)$ digits, so just *writing down the value when you know it* has linear bit complexity. What's more, the matrix entries end up eventually having $O(n)$ digits too, which eventually slows down the arithmetic operations subsumed into the latest matrix multiplication operation.
> 9 votes

# Answer
There are two good answers already, but there are two points that weren't touched on. One is that of **output-polynomial time**. A lot of theoretical CS concerns itself purely with *decision* problems, where the output is just a single bit; these are *languages* Sometimes instead you want a whole many-bit output, like multiplying two matrices; these are *function problems*.

Both of the examples you gave (outputting "Hello world" *n* times, or printing out 1 through *n*) have a very large output. Since there are plenty of problems where the desired output is very large, it can be valuable to turn the attention from "How long does it take my code to run" to "How long does it take *per byte of output*?". If I can generate the next byte of output in polynomial time, then it's "output-polynomial time" algorithm.

For example, if you want me to enumerate all the permutations from 1 to 10, I'll have 10! permutations to output. A naive algorithm might start with \[1,1,1,1,1,1,1,1,1,1\], recognize that it's not a permutation, and move on to \[1,1,1,1,1,1,1,1,1,2\], and so on. When it reaches \[1,2,3,4,5,6,7,8,9,10\], it will output that, then move on to \[1,2,3,4,5,6,7,8,10,1\] and so on. For permutations of 1 to *n*, this takes $n^n$ time, as compared to the $n! \approx (n/e)^n$ output size. Thus this runs in approximately $S^{1 + \frac{1}{\log(n)}} \< S^1.1$ time, and is output-polynomial. Smarter enumeration algorithms can do it in $Sn$ time, which only has *polynomial overhead* (in $n$) over the output size. This so-called "output-sensitive analysis" is useful when the size of the output might not be easily known ahead of time. This paper is an example of recent work of this type: given points in a plane, connect them into a non-self-intersecting polygon. It's easy to find one way, and there may be very few ways or very many ways (like $n!$ many). An $n!$ algorithm is no good if there's actually only, say, 3 solutions to print out, so we want something that scales with the output size.

The other thing I wanted to mention is the importance of *unary encoding* in complexity theory. In very precise (that is, very mathematician-oriented) definitions of some problems, authors will specify that some input number $k$ must be specified in unary. This way, an algorithm will be polynomial time if it runs in $poly(k)$, as opposed to needing to run in $poly(2^k)$ (which it would need to do if $k$ was in binary). For example, SUBSET-SUM can be solved in polynomial time, if all the numbers are written in unary.
> 3 votes

# Answer
You are correct; time complexity in theoretical computer science is usually measured in terms of the size of the input1.

This imposes a wrinkle for working programmers using time complexity to reason about their algorithms' performance. As you note, a lot of operations on numbers have higher complexity than a programmer would expect because numbers of high magnitude can be represented in a small amount of space and CPUs implement basic operations as single instructions. To a programmer, comparing two integers for equality is a (very cheap) constant time operation. To a computer scientist it requires linear time (in the size of the representation of the integers, not in their magnitude)!

But the basic idea of using big-oh complexity to measure running time *fundamentally* relies on inputs being arbitrarily large, and even the basic theoretical notions of whether problems are computable or not relies on the input space being infinite. Whereas the way primitive numeric types work in actual CPUs relies on them being fixed-size units that therefore have a bounded size and a finite number of possible values.

In big-oh complexity analysis we're giving an expression that will bound the runtime as inputs grow arbitrarily large. If the input is a single number expressed in a primitive machine type, the largest possible input is a constant, and thus the largest possible runtime is *also* a constant. Many problems would thus have "degenerate" $O(1)$ runtime if analysed this way. Additionally every problem that has only a finite number of cases is decidable, because a big (but finite) mapping table would decide it. The halting problem where the input is a positive integer that identifies a Turing machine, is undecidable. The variant halting problem where the input is a positive integer that fits in 64-bits is decidable and can be implemented in $O(1)$ runtime; but this is a useless result that doesn't *help* anyone! (because the mapping table that would decide it is impractically vast, even though technically finite, and actually figuring out all the entries that should go in the table is probably impossible in the real world)

So basically, the standard tools of this sort of computer science theory just aren't useful to analyse algorithms where the input can only be a *primitive* machine integer. They don't *usefully* divide problems & algorithms into different classes unless we are considering problems that have an infinite space of inputs that can be of unbounded size. And primitive numeric types as implemented in actual CPUs and programming language *don't* meet this criteria. It is fundamentally impossible to do constant-time comparisons and basic arithmetic on numbers of unbounded size, CPUs can only do it because they work with *bounded* numbers.

For example, taking a number $n$ and printing the numbers from $1$ to $n$ is **not** $O(n)$ if we're being fully general. Simply incrementing a number that is of unbounded size (and might require many many more than 64 bits to represent) in the worst case requires us to traverse all of the digits. Even if we assume each 64-bit chunk of bits can be handled all at once in a single operation, the number of 64-bit chunks is linear in the representation size of $n$ (which is logarithmic in $n$ itself). But if we constrain our program to only take an $n$ that can fit in a single 64-bit word, then the worst case runtime is $O(2^{64})$ which is also $O(1)$ since constant factors aren't relevant to big-oh analysis.

For a *real* algorithm that takes a number as input to match up with the this kind of theoretical analysis, the input needs to be not a primitive type like a 64-bit integer, but rather an arbitrary size (and/or precision) number; a lot of languages have "bignum" types and libraries that support this. These effectively use primitive machine types as digits in a base $2^{64}$ (or whatever) number system; numbers are variable length sequences of symbols rather than single symbols, and operations like arithmetic and comparisons take time proportional to the number of "digits" rather than being constant time.

Most of the time real programs simply don't *need* to ever be given inputs large enough to require arbitrary-precision numbers. For example your "print every number from $1$ to $n$" program is already getting up to the scale of the age of the universe to run just with the largest possible 64-bit numbers (depending on exactly how many we can print a second). So programmers take the shortcut of just assuming they'll only ever need a number that is a single "digit". That shortcut makes lots of algorithms much "faster" than we would get from analysing them as if they were Turing machines reading numbers encoded in an unbounded number of symbols, but technically this is only because they don't actually solve the **infinite** problem such a Turing machine would solve, only the finite number of cases that we care about in practice.

If we're being very pedantic this issue applies with almost all programs, not just ones involving numbers. Real programs run on an actual machine always have a finite bound on the amount of memory they can use, which stops them from actually being able to solve problems of arbitrary size, and thus technically makes their "real" complexity degenerate. But analysing a string-processing algorithm **as-if** the strings could be unbounded still produces useful knowledge because programmers are simply *used* to thinking about strings as variable-sized with operations on them taking time dependent on the size of the string. The point where the big-oh bound takes over and dominates any lower-order term (that can be larger for small inputs) tends to in practice occur at small enough magnitudes that it's still well within the scale of inputs that actually occur, and so it produces useful results to take the classifications we get from analysing idealised infinite-capacity algorithms and applying them to algorithms that will run on real machines implemented in real programming languages.

But if you're processing numbers and only accepting numbers with a finite bound, you need to do a different analysis with different assumptions than standard basic complexity analysis. Giving your runtime bound in terms of the magnitude of the input rather than the size of its representation and assuming basic operations are constant time can produce quite reasonable results for a working programmer; they would be technically wrong as general statements for infinite problems requiring unbounded input, but if that's not what you actually want to analyse it doesn't necessarily matter much.

---

1 If we're being properly rigorous we really should, as Caleb's answer points out, explicitly consider and state what variable we're actually using in the expression we're using to bound the input. It doesn't *have* to be the size of the input but that's usually the "default", especially in informal discussions like those that tend to be made by programmers rather than academics.

There's also some subtleties in what quantity is actually being bounded by the big-oh expression too. For example most programmers with any exposure to complexity theory have heard of the idea that an optimal comparison-based sorting algorithm has time complexity $O(n \cdot \log n)$. But what is often missed is that this bound is abstracting over the actual size of the items being sorted and the time it takes to compare them. This is **not** a bound on the total number of operations in running the sorting algorithm. $n$ in this expression is the number of items to be sorted, and the quantity being bounded is the number of *comparisions* that will be needed (regardless of the number of operations it takes to compare two items).
> 1 votes

---
Tags: complexity-theory, time-complexity, algorithm-analysis, runtime-analysis
---


# Question
Title: Finding corresponding node in a duplicate binary-tree
Given two duplicate binary trees (see the embedded picture), you are given a node in Tree A, find the same corresponding node in Tree B.

I believe the optimal approach should be traversing both trees at the same time, and when you reached the node in Tree A, you would know you have also reached the same node in Tree B.

Code example to solve this issue would be appreciated.

# Answer
I'm not going to provide a code example. Your approach would work, and takes time proportional to the *size* of the tree (i.e., its number of vertices) in the worst-case. This can be improved to only take worst-case time proportional to the depth of the vertex of interest. If the tree is balanced, there would be an exponential difference in the running times.

Keep track of the path from the node of interest to the root $r$ of Tree $A$. In particular, for each node $x \neq r$ of the path, push into a stack $S$ either $L$ or $R$ depending whether $x$ it is the left or right child of its parent.

Then, start from the root of Tree $B$, iteratively pop from a value $y$ from $S$ and move to the left or right child depending on whether $y=L$ or $y=R$, respectively. The node you're at when the stack is empty is exactly the node you're looking for.
> 0 votes

# Answer
If upward links are available, trace the path from $n\_A$ to the root $r\_A$, then trace back from $r\_B$ to $n\_B$. Otherwise, traverse $A$ until you find $n\_A$ (using your favorite method), while keeping a trace of the path, or performing the same moves in $B$.

Note that a path can be represented as a mere bit string telling left or right on every level. (A foolish solution could even avoid storing the bit when a node has a single child.)

The first method requires a string as long as the depth of $n\_A$ (used as a LIFO queue). It can be implemented recursively for this purpose.

The second method requires a string as long as the deepest depth reached during the traversal (FIFO queue).

The third does not need a representation of the path.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Question about how can i determine if counting sort is the right option over other sorting algorithms
So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm.

Now i find that solutions for that question given by my professors are wrong because they do gave this as answer:( pseudocode)

```
Sorting(A,k) //where k is a value inserted by the user(?)
{
max=a[0];
for i=1 to n // n=dim
{
    if( a[i] > max) update max with a[i]
}
if( max <= k*n) then countingsort(A)

else heapsort(A);

return A;

```

Now that being said, if k is really a value inserted by the user, this makes that solution not really case sensitive or a proper valuation of counting sort time complexity. It seems to me that it isnt a general algorithm, which should be instead the purpose of that exercise i guess. my solution is:

```
Sort(A){
    int max, i;
    int min;
    if( arr[0] > arr[1]){
        max=a[0];
        min=a[1];
    }

    for(i= 2 ; i < n ; i++){
        if(a[i] > max) max=arr[i];

        else if( a[i]< min) min=arr[i];
    }
    range= max-min; // range for counting sort
    if(range/n < log n) counting sort(A,range);

    else mergesort/heapsort(A......);

    return A;
    }

```

If (range/n) \< logn , it means that range \< nlogn, which implies it ""should"" be better than other optimal sorting algorithms. It might be not the most accurate way but it seems like it should be something like that, shouldnt it?

# Answer
> 0 votes
I wouldn’t be too happy with your professor’s solution. You noticed that it will refuse to do a very fast counting sort if all item are either n*k+1 or n*k+2. That’s bad. What is fatal is that it will always do a counting sort if the array elements are all negative. (Please don’t tell me that a sorting algorithm which can only handle positive numbers would ever be considered).

PS It seems there was an attempt to fix the code since I wrote my answer. As a result it became a lot worse since in half the cases min and max start out as being undefined. Plus memory used can be up to n log n.

# Answer
> 0 votes
The professor's solution differs from yours in an important way: it limits the memory size to $kn$, where $k$ is chosen by the user. Your solution does not offer this control and might lead to memory overflow.

---
Tags: complexity-theory, algorithm-analysis, sorting
---


# Question
Title: Efficient ways to sort pairwise distances for set of points in Euclidean space?
Consider a Euclidean space $\mathbb{R}^d$. Consider $ X \subset \mathbb{R}^d$ where $X$ is a finite set with $|X|=n$. Consider the set of line segments $\\{xy | x,y \in X\\}$ . I have a process $Z$ that I want to apply to each line segment, from smallest to largest but I will stop examining line segments when a line segment satisfies some condition $C$.

One thing I could do is find all line segments and then order them from smallest to largest and simply apply $Z$ to each line segment until $C$ is satisfied but organising the line segments will have $O(n^2\log (n))$ complexity.

Is there an efficient way I can find each line segment in order of increasing length, one at a time.

That is, find a line segment $l$, apply $Z$ to $l$ and if $C$ is not satisfied find the next largest line segment, apply $Z$,...

Thank you in advance

# Answer
> 2 votes
A better solution could be as follows:

1. Create a min heap over $n^2$ line segments.
2. Take the top element of the heap, check if it satisfies condition $C$. If it does not satisfy it, pop it out. If it satisfies the condition, stop.

Step $1$, take $O(n^2)$ time. Step $2$ takes $O(p \log n)$ time, where $p$ is the position of the first line segment in the sorted order that satisfies the condition $C$.

If $p$ is small, the algorithm takes $O(n^2)$ time.

---
Tags: algorithms, efficiency, euclidean-distance, ordering
---


# Question
Title: How to solve a linear programming problem
Given a problem (D, c, Min) with admissible set D={(x,y)∈R2 : |y+√3x|≤2√3,|y-√3x|≤2√3,|y|≤3} and the price function c(x, y) = x + 2y. Translate the given problem to a linear program in standard form. Determine the corresponding matrix A and the vectors ⃗b and ⃗c respectively.

# Answer
> 0 votes
Your main goal here is to rewrite your constraints as **linear constraints**. There is a good ressource to do such a translation here.

You're lucky here as your constraints are of the form $|L| \leq C$ where $L$ is a linear combination of your variables and $C$ a constant. It simply can be written as two linear constraints : $$ |L| \leq C \iff \begin{cases} L \leq C \\ -L \leq C \end{cases} $$

For example, you can rewrite one of your constraints as :

$$ \left|y + \sqrt3 x \right| \leq 2 \iff \begin{cases} y + \sqrt3 x \leq 2 \\ \- y - \sqrt3 x \leq 2 \end{cases} $$

I think you can do the other constraints now. Good luck!

---
Tags: linear-programming
---


# Question
Title: Efficient algorithm to translate/shift polynomials
I have a polynomial $P(x)$, and given some constant $d$, I need to find the polynomial $P(x+d)$. For example, if $P(x)=x^2$ and $d=1$, then the result would be $P(x+1)=(x+1)^2=x^2+2x+1$ (with the coefficients stored in an array/vector).

I know the algorithm with $O(n^2)$ time complexity, which is based on Horner's method: $$a\_0+(x+d)(a\_1+(x+d)(a\_2+...+(x+d)a\_n))$$ However, it is not efficient enough for my needs. Is there an algorithm that is more efficient for solving this problem?

P.S. The coefficients and $d$ will always be integers, if that helps.

# Answer
> 6 votes
Use FFT. Suppose that $\deg P \leq n$ and we use FFT on $n$ points (usually $n$ would be the smallest power of 2 which is at least $\deg P$). Let $\omega$ be an $n$th root of unity. The Fourier coefficients of $Q(x) = P(x+d)$ are $$ \hat{Q}(m) = \sum\_{i=0}^{n-1} Q(i) \omega^{mi} = \sum\_{i=0}^{n-1} P(i+d) \omega^{mi} = \sum\_{i=0}^{n-1} P(i) \omega^{m(i-d)} = \omega^{-md} \hat{P}(m). $$ This shows how to compute the Fourier transform of $Q$ from that of $P$ in linear time. Since FFT takes time $O(n\log n)$ (for suitable $n$), the overall running time is $O(n\log n)$. Choosing $n$ as indicated above, this becomes $O(\deg P \log \deg P)$.

# Answer
> 2 votes
Here's another FFT-based approach that I can confirm works. This builds off of Algorithm F in Fast algorithms for Taylor shifts and certain difference equations and has a natural extension to multivariate polynomials and shifts

Assuming our polynomial is of degree $n$, given the polynomial coefficient vector ${p\_k}$ and a shift $a$, we'll construct the intermediate polynomial coefficient vectors

$$ \begin{align} u\_k &= (n-k)!\ p\_{(n-k)} \\ v\_k &= a^k / k! \end{align} $$

By treating these as polynomial coefficients and taking their direct convolution, $g\_k$ (which an be done in $O(n \log{n})$ time via FFT with appropriate zero-padding) we get our final polynomial coefficients as

$$ q\_k = g\_{(n-k)} / k! $$

Here's Mathematica code for that

```
fourierConvolve[c1_, c2_] :=
 InverseFourier[
  Fourier[PadRight[c1, Length@c1 + Length@c2 - 1], FourierParameters -> {1, -1}] *
    Fourier[PadRight[c2, Length@c1 + Length@c2 - 1], FourierParameters -> {1, -1}],
  FourierParameters -> {1, -1}
  ]

tayShiftFourier[coeffs_, a_] :=
 With[{
   nco = Length@coeffs - 1
   },
  fourierConvolve[
     Reverse[coeffs*Factorial[Range[0, nco]]],
     a^Range[0, nco]/Factorial[Range[0, nco]]
     ][[nco + 1 ;; 1 ;; -1]]/Factorial[Range[0, nco]]
  ]

```

As noted, this generalizes easily to multivariate polynomials. Considering that one could apply this approach to each dimension recursively, we pretty naturally find that we can replace our coefficient sequence $P$ with a tensor of coefficients, our factorials can be replaced with the outer-product tensor of factorials in each dimension, and the powers of the shifts

Here's the N-dimensional analog of the prior code, although I did some small modifications in orders of operations to avoid having to reverse my coefficient tensors

```

Clear[tayShiftFourierND, fourierConvolveND];
fourierConvolveND[c1_, c2_] :=
  InverseFourier[
   Fourier[
     ArrayPad[c1, {0, # - 1} & /@ Dimensions[c2]],
     FourierParameters -> {1, -1}
     ]*
    Fourier[
     ArrayPad[c2, {0, # - 1} & /@ Dimensions[c1]],
     FourierParameters -> {1, -1}
     ],
   FourierParameters -> {1, -1}
   ];
tayShiftFourierND[coeffs_, shift_] :=
 Block[
  {
   ncos = Dimensions[coeffs] - 1,
   facTensor,
   shiftTensor,
   revFacTensor,
   convolvedCoeffs
   },
  facTensor = Outer[Times, ##] & @@ Table[Factorial[Range[n, 0, -1]], {n, ncos}];
  shiftTensor =
   Outer[Times, ##] & @@ MapThread[#^Range[#2, 0, -1] &, {shift, ncos}];
  revFacTensor = Map[Reverse, facTensor, Range[0, Length@ncos - 1]];
  convolvedCoeffs = fourierConvolveND[
      coeffs*revFacTensor,
     shiftTensor/facTensor
     ][[Sequence @@ Table[n ;;, {n, Dimensions@coeffs}] ]];
  convolvedCoeffs/revFacTensor
  ]

```

and here's some proof that it works

```
coeffs3D = BlockRandom@RandomReal[{-10, 10}, {5, 3, 4}];
poly3D = Total@
   Flatten[coeffs3D*Outer[Times, x^Range[0, 4], y^Range[0, 2], z^Range[0, 3]]];

tayShiftFourierND[coeffs3D, {1, 2, 3}] // Chop // Flatten // Norm

4976.12

poly3D /. {x -> x + 1, y -> y + 2, z -> z + 3} // Expand //
    CoefficientList[#, {x, y, z}] & // Chop // Flatten // Norm

4976.12

```

where I just used the norm of the flattened tensor of polynomial coefficients after shifting as effectively a hash

---
Tags: algorithms, polynomials
---


# Question
Title: Defining multi commodity flows as polytopes
In a multi commodity network, we define a demand to be a vector $d \in \mathbb{R}^{k}$, where $k$ is the number of pairs of sinks. That is, $k = \binom{S}{2}$, where $S$ is the set of sinks (aka terminals).

For example, if $\left| S \right| = 3$ we have $\binom{3}{2} = 3$ possible pairs of sinks. A demand can be of the type $\left\< 1, 0,\frac{1}{2}\right\>$. It translates to "Need flow $1$ for the first couple" and "need $0$ flow for the second couple" and "need $\frac{1}{2}$ for the third couple". All $3$ conditions are to be satisfied simultaneously.

For a given flow network a demand is said to be *feasible* if we can find a flow function to achieve it, while maintaining the capacity constraints and all normal flow rules.

We define the set of all feasible demands as $D = \left\\{ d \in \mathbb{R}^{k} | d \text{ is feasible}\right\\}$.

I have recently came across a statement which says $D$ can be seen as a polytope in $\mathbb{R}^{k}$, yet I find this statement a bit puzzling. Is there a proof for this, or even perhaps an intuition behind it?

(Perhaps, it is easy to show for the example of $\left| S \right| = 3$)

**Note**: full definitions can be seen here.

# Answer
It is a polytope because it can be expressed as a system of linear inequalities. See https://en.wikipedia.org/wiki/Multi-commodity\_flow\_problem. In particular, let $d$ be a demand and $f$ a flow; there is a system of linear inequalities on $d,f$ that capture the condition that $f$ is a legal flow that achieves $d$. It follows that the set

$$S = \\{(d,s) \mid f \text{ is a legal flow that achieves } d\\}$$

is a convex polytope. Moreover, the set $D$ has the form $D = \\{d \mid (d,s) \in S\\}$, and the projection of any polytope onto fewer dimensions is itself a polytope. Therefore, $D$ is a polytope.

---

If that sounds like a lot to absorb, here is an elementary proof that $D$ is convex, which might help give some partial intuition:

Suppose $d\_1,d\_2$ are two feasible demands. Let $f\_1$ be a legal flow that achieves demand $d\_1$, and $f\_2$ a legal flow that achieves $d\_2$. Let $\lambda$ be any real number with $0 \le \lambda \le 1$. Define $d\_3 = \lambda d\_1+ (1-\lambda) d\_2$ and $f\_3 = \lambda f\_1 + (1-\lambda) f\_2$. It is easy to verify that $f\_3$ is a legal flow, and that it achieves demand $d\_3$. It follows that $d\_1,d\_2 \in D$, then $\lambda d\_1 + (1-\lambda) d\_2 \in D$, for all $\lambda$ with $0 \le lambda \le 1$. This proves that the region $D$ is convex.
> 0 votes

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


title: is $IP=BPP^{NP}$

text:
# Question
Title: is $IP=BPP^{NP}$
In the class $IP$ we have a probabilistic polytime verifier which interacts with a nondeterministic prover polynomial times and all the messages are of length polynomial of the input. We can think of this as a $BPP$ machine asking queries to a $NP$ oracle and doing its computation. All the interactions the verifier does and the messages got from the prover can be obtained by polynomially many steps from an $NP$ oracle. So overall the time complexity is still polynomial. Similarly, in any computation of $BPP^{SAT}$ machine, we can think of the verifier asking the prove the queries. Here the interactions are the queries made by the verifier.

Intuitively it feels that $IP=BPP^{NP}$ but is that true?

# Answer
If $BPP = P$ (as is widely believed), then $BPP^{NP} = P^{NP}$. Since $IP = PSPACE$, $BPP^{NP} = IP$ would mean that $P^{NP} = PSPACE$, which seems unlikely (e.g. polynomial time hierarchy would collapse). Furthermore, Sipser–Lautemann theorem shows unconditionally that $BPP \subseteq NP^{NP}$, which means that $BPP^{NP} \subseteq (NP^{NP})^{NP} = NP^{NP}$. Thus $BPP^{NP} = IP$ would imply that $NP^{NP} = PSPACE$, which again seems unlikely for the same reasons as $P^{NP} = PSPACE$ seems unlikely.

Speaking more informally, your description of $IP$ is incorrect, since the prover is not limited to solving problems that are in $NP$ (nor is it non-deterministic in any sense). In fact, the prover is assumed to have unlimited computational power (e.g. it can solve the Halting problem). The trick is that it needs to be able to convince the Verifier with good probability (over the coins of the Verifier) that the solution it gave is correct.
> 2 votes

---
Tags: oracle-machines, interactive-proof-systems, probabilistic-turing-machines
---


# Question
Title: Is it possible to have a 2 by 2 rigid framework without having a corresponding connected bipartite graph?
According to the theorem(see reference) on the rigidity of frameworks:

> A rectangular framework is rigid if and only if its associated bipartite graph is connected.

Now consider the case for a 2-by-2 rectangular framework.

In this case, if we draw a brace in the first and the third squares, the framework becomes rigid (since, by observation, none of the smaller squares can be skewed without skewing the braced squares).

However, the resulting bipartite graph is not a connected one. Since the theorem establishes an one-to-one correspondence between the associated bipartite graph being connected and the rigidity of framework, the example that I have come up here surely violates the theorem.

What am I getting wrong here?

---

**Reference:**

Theorem 1.4.1, Gross, J. L., & Yellen, J. (2005). Graph Theory and Its Applications. In Chapman and Hall/CRC eBooks. Informa. https://doi.org/10.1201/9781420057140

# Answer
> 1 votes
The picture shows that the given framework is not a rigid framework since it can be skewed in the following manner:

---
Tags: graphs, bipartite-graph
---


# Question
Title: Prove that the language L = { <T> : T is a Turing machine that runs in polynomial time } is not Turing-recognizeable
* By "$T$ runs in polynomial time", I mean that $T$ halts for every input of length $n$ in $O(n^k)$ steps for some $k$.
* By Turing-recognizable, I mean that there exists a Turing machine that halts in the accept state iff the input $w = \langle T\rangle \in L$.

I'm not really sure how to approach this problem. It seems like I should reduce from $A\_{\text{TM}}$ (or $HALT\_{\text{TM}}$ depending on convenience). *(Edit: wrong, both of these are Turing-recognizable.)*

I also tried to directly do a running time variant of the diagonalization proof that $A\_{\text{TM}}$ is undecidable. I began by assuming that $L$ is Turing-recognizable by some $M$. Then we can create a TM $D$ that reads $\langle T\rangle$ and simulates $M$ on it. Towards contradiction we then make $D$ run in a loop (or do $2^{|\langle T\rangle|}$ additional steps) if $\langle T\rangle \in L$, or halt immediately otherwise. But this doesn't work as we don't know the complexity of $M$. More precisely I can get a contradiction only if $\langle M\rangle \in L$.

Rice's theorem doesn't seem to be of much help either. If I could prove that (1) $L$ is undecidable and (2) $L^C$ is recognizable, then I would obtain $L$ is unrecognizable. But Rice doesn't help with (1) (because for $L(T\_1) = L(T\_2)$ says nothing about the running times), and (2) seems to be straight-up false.

# Answer
> 1 votes
The simplest example of a non-Turing-recognizable language is the complement of $A\_{\text{TM}}$, $$\overline{A\_\text{TM}}=\\{\langle M,w\rangle\mid M\text{ is a TM and }M\text{ does not accepts }w\\}.$$

Let us reduce $\overline{A\_\text{TM}}$ to $L$.

---

Given a TM $M$ and a string $w$, construct the following TM.

$M'$= "On input $s$:

1. Simulate $M$ on input $w$ for $|s|$ steps using less than $|s|^3+159759$ steps.
2. If the simulated $M$ has accepted, possibly before $|s|$ steps, run forever. Else halt."

Here $3$ and $159759$ just mean some large-enough numbers independent of $M$ so that the simulation for $|s|$ steps can be done.

Let us verify that $\langle M,w\rangle\in \overline{A\_\text{TM}}$ iff $\langle M'\rangle\in L$.

* If $\langle M,w\rangle\in \overline{A\_\text{TM}}$, i.e., $M$ does not accept $w$, then on input $s$, $M'$ will always halt in $|s|^3+159759$ steps. Hence $\langle M'\rangle\in L$.
* If $\langle M,w\rangle\notin \overline{A\_\text{TM}}$, i.e., $M$ accepts $w$, then for input $s$ that is long enough, the simulated $M$ will have accepted after step 1. Hence $M'$ will run forever on those input. Hence $\langle M'\rangle\notin L$.

Since $\overline{A\_{\text{TM}}}$ is not Turing recognizable, neither is $L$.

# Answer
> 0 votes
Suppose $L$ is decidable with a Turing machine $T$. Now we will show $\sim HALT\leq L$.

Create a Turing machine $\mathcal{M}$ from $\langle M,x\rangle$ which on any input runs $M$ on $x$ for $|x|$ many steps. If $M$ halts within $|x|$ many steps then $\mathcal{M}$ goes on a loop and halts after $2^{|x|^c}$ many steps for some constant $c\>1$ and if $M$ does not halt within that many steps $\mathcal{M}$ halts.

Now it is easy to see that $\mathcal{M}$ is a polynomial time Turing Machine if $M$ halts within $|x|$ steps. Therefore $$\langle M,x\rangle\in\ \sim HALT\iff \mathcal{M}\in L$$Since $T$ can decide $L$, $T$ can decide if $\mathcal{M}$ is in $L$ or not, i.e. $T$ can decide the set $\sim HALT$. Which is not decidable. Hence contradiction. Hence $L$ is not decidable

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


# Question
Title: Does a problem remain tractable If a single discrete variable becomes continuous?
Let $\mathcal{F}$ be a family of pairs of the form $(A,b)$, where $A$ is an integer matrix and $b$ is an integer vector with the same number of rows. For every integer $k$, define $L(\mathcal{F}, k)$ to be the following family of decision problems.

> INPUT: a pair $(A,b)\in \mathcal{F}$.
>
> OUTPUT: "True" if there exists a real vector $x \geq 0$ satisfying $A x \leq b$, where for every $i \> k$, $x\_i$ must be an integer (for $i\leq k$, $x\_i$ can be any real number).

If $k=0$, then these are simply integer programming problems, and $L(\mathcal{F}, k)$ is NP-hard in general. But it is in P for some subclasses of matrices and vectors, for example, when for all $(A,b)\in \mathcal{F}$, the matrix $A$ is of totally unimodular.

I am interested in the effect of $k$ on the complexity of $L(\mathcal{F}, k)$. In particular, if $L(\mathcal{F}, k)$ is in P for some $k$, does it imply that $L(\mathcal{F}, k+1)$ is in P too?

Stated informally: if we take a single discrete variable and allow it to be continuous, does the problem remain tractable?

**EDIT**: Here is an example showing that the opposite *is* possible: if we start from an NP-hard problem, and convert a single discrete variable to continuous, the problem may become tractable. Consider the following family of linear programs: $$ a\_1 x\_1 + \cdots + a\_n x\_n = (a\_1+ \cdots +a\_n)/2 \\ 0 \leq x\_i \leq 1 ~~~ \forall i\in\\{1,\ldots,n\\} \\ x\_i \in \mathbb{Z} ~~~ \forall i\in\\{1,\ldots,n\\} $$ where the input is the integer vector $a\_1,\ldots,a\_n$ and the output is "true" if there is a vector $x\_1,\ldots,x\_n$ satisfying the constraint. This LP represents the NP-hard partition problem.

Suppose w.l.o.g. that the input arrives in descending order ($a\_1\geq \cdots \geq a\_n$). Then, if we allow a single variable $x\_1$ to be continuous (we remove the constraint $x\_1\in \mathbb{Z}$), then the problem becomes tractable: if the largest item can be split, then the answer is always "yes". So, $L(\mathcal{F}, 1)$ is in $P$ while $L(\mathcal{F}, 0)$ is NP-hard.

Is there an $\mathcal{F}$ for which the opposite holds --- $L(\mathcal{F}, 1)$ is in $P$ while $L(\mathcal{F}, 0)$ is NP-hard?

EDIT 2: Note that, without the restriction to linear problems, even making *all* variables continuous might make a problem harder. See this answer.

# Answer
> 1 votes
If a linear program has some integer and continuous variables, then the problem is known as *Mixed-Integer Linear Program*. Moreover, if the number of integer variables are constant, then the problem can be solved in polynomial time (see Proposition 8.1 from here).

Therefore, if any $L(\mathcal{A}, \mathcal{B}, k)$ is in $\mathsf{P}$ for some $k$, and suppose that $n-k = O(1)$ where $n$ is the number of elements in $x$. Then, it trivially implies that $L(\mathcal{A}, \mathcal{B}, k+1)$ is in $\mathsf{P}$ too, since $L(\mathcal{A}, \mathcal{B}, k+1)$ can be solved in polynomial time (there are at most $n-k-1 = O(1)$ integer variables in $L(\mathcal{A}, \mathcal{B}, k+1)$).

---
Tags: complexity-theory, linear-programming
---


# Question
Title: Can you transform 3sat (or equivalent) into another satisfiability problem that increases the ratio of solutions to non-solutions
Say I have f(x1,x2,x3,...) where the output is either 0 for all inputs (unsatisfiable) or a variable boolean output of 0 or 1 depending on the input (satisfiable). Let's not consider functions that are always satisfiable)

If I don't know whether f is satisfiable or not:

Can I find a function f' (in polynomial time), such that if f = 0 for all outputs, then f'= 0 for all outputs as well. But if f is satisfiable, then the ratio of 1s to 0s is increased (unless f is always satisfiable). In other words increase this ratio (total amount of 1s)/(total search space). Also, the increase in ratio should be in such a way that it can reach a ratio of 1/2 after a polynomial amount of iterations.

The reason I'm asking, is because if I can, then there is a significant speedup to solving 3sat on quantum computers (using deutsch-yoza).

# Answer
The answer is probably no. Because if this were the case we would have a polynomial time randomized solution to 3-sat (as mentioned by steven in the comments), and we haven't found that yet.
> 2 votes

---
Tags: complexity-theory, np-complete, np-hard, satisfiability, 3-sat
---


# Question
Title: Find a weight threshold for edges for maximum number of connected components in a graph
So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or equal to W gets removed, which results in the maximum amount of connected components. A connected component is defined as at least two connected nodes.

I've thought about sorting all the weights of the edges from high to low, then iterating through that list and setting the treshold equal to the current weight and check if the current amount of components is the highest amount we've had thus far.

Would this be an efficient algorithm? Also, the graph is undirected.

Added: If two tresholds W1 and W2 produce the same maximum amount of components, then the treshold for which the least amount of nodes are in a connected component is chosen. In other words, the treshold for which there are the most amount of free nodes.

Clarifications: The application is a graph for plagiarism detection. Each pair of nodes has a weighted edge connecting them, where the weight represents the probability of plagiarism between the two. A "free node" is defined as a node that is not connected with any other node.

Let's say the treshold is a weight of 80. When a node (which represents some submission) doesn't have an edge with weight higher than 80 to any other node, it's a free node.

# Answer
Let $W = \\{w\_1, \dotsc, w\_m \\}$ be the set of weights (assume that all weights are different for simplicity). Without loss of generality assume that $w\_1 \> w\_2 \> \dotsc \> w\_m$, and the graph is connected. Note that the sorted order can be obtained in $O(m \log m)$ time.

An efficient algorithm can make use of union-find data structure as follows:

1. Start with threshold of $w\_1$. In this case, the graph has only a set of free nodes. Thus, the number of connected components are 0 (as per the definition of a connected component given in the question). Let $num$ denote the number of connected components. Initially $num = 0$.
2. Repeat the following for every $w\_i$ in order $(w\_2 \to w\_3 \to \dotsc w\_n)$: add $w\_i$ weighted edge to the existing graph. Let $w\_i$ is incident on vertices $u$ and $v$. There are four possible cases:

* If $u$ and $v$ belongs to different connected components, update $num \leftarrow num -1$.
* If both $u$ or $v$ are free nodes, update $num \leftarrow num + 1$.
* If $u$ and $v$ belongs to the same connected components, $num$ stays the same.
* If exactly one of $u$ or $v$ is a free node, then $num$ stays the same.

This procedure gives number of connected components for every threshold $w\_i$. Choose the one that gives the maximum number of connected components.

Using the union-find data structure, the above procedure can be implemented in $O(|V| \log |V| + m)$ time (as per aggregate analysis). Thus, the overall running time is $O((|V| + |E|) \log |V| ))$, where $|E| = m$ denote the number of edges and $|V|$ denote the number of vertices.
> 0 votes

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