# Question
Title: "Natural" reductions vs "Polynomial-time many-one" reductions (Karp Reductions)
For two problems $A$ and $B$ and a **Karp** Reduction $R$ from $A$ to $B$, we call the reduction $R$ **natural** if, for any instance $I$ of problem $A$, the size of $R(I)$ (as well as the possible numerical parameters of $R(I)$ depends only on the size of $I$ and the sizes of $I$ and $R(I)$ are polynomially related.

We know that all the text-book reductions (from SAT to 3-SAT, 3-SAT to Vertex Cover, Hamiltonian Cycle etc.) are **natural** in the above sense. In fact, all the natural known "NP-complete" problems are complete under "**Natural**" reductions.

I have following two questions:

1. Is it possible for a Karp-reduction to be "**non-natural**" in the above sense?
2. Are "**natural**" reductions only a special case of "Karp" reductions or Can we generalize them for other reductions (like logspace or linear time reductions)?

To understand the context better: Kabanets-Cai\[1999\] in his seminal paper proved that Minimum Circuit Size Problem (popularly known as MCSP) being NP-hard under so-called "**natural**" reductions leads to class $E$ having superpolynomial circuit size. Then, recently Murray-Williams\[2015\] proved that MCSP being NP-hard under "**Polynomial-Time**" reductions leads to $EXP \neq NP \cap P/poly$ (This is weaker than Kabanets-Cai result). So, surely "natural" reductions are more strict than "polynomial-time" reductions. (or Am I missing something here?)

# Answer
Natural reductions are a special case of Karp reductions, with an extra condition stating that the output's length depends only on the input's length (and not structure). This concept can be applied to many forms of many to one reductions, so I guess you could talk about natural logspace reductions.

Obviously a karp reduction can be non-natural (otherwise the definition would be of no use). Think about a reduction from clique to SAT, I can make it non natural by first checking whether the graph is planar, and in case the answer is yes output some fixed non satisfiable formula (suppose the parameter $k$ is greater than $4$). This breaks naturality, since now the output formula's length depends on the planarity of the input graph.

Finding an example of a "natural" non-natural reduction (even if a natural one is known) is harder, but I guess that if you go over enough reductions you will find one.
> 4 votes

---
Tags: complexity-theory, reductions, lower-bounds
---


title: Revolutions in Computer Science

text:
# Question
Title: Revolutions in Computer Science
# TL;DR

What revolutions have there been in computer science, which entirely changed our view about the subject, due to 'one way of thinking' being replaced by 'a new (incompatible) way of thinking' (such as Einsteinian physics replacing Newtonian physics).

---

To explain a bit further:

I was trying to think about revolutions in computer science, and which one there have been. To clarify on what I mean by scientific revolutions:

> "Those non-cumulative developmental episodes in which an older paradigm is replaced on whole or part by an incompatible new one" (Kuhn, 1970 p.92)

To give perhaps the most famous example. Einstein's theories of relativity have shown that Newtonian physics is incorrect (it makes metaphysical assumptions, which turned out to be wrong). The paradigm in which General Relativity operates is incompatible with the Newtonian mechanics. Which then led to the reconstruction of science (Vienna circle).

A friend of mine (I believe correctly) pointed out that Quantum Computing could be one such revolution in computer science. But it has not actually happened yet.

As a software engineer myself, every time I thought of something that I'd consider a revolution, I became unsure if it really was a revolution as the 'paradigms' (methodologies) are not actually replaced and often even compatible with older ways of doing things. And some are pure technological advances (Functional programming after OO, or OO after procedural). Perhaps the application of Lambda Calculus in computer science (programming languages, type theory, ..?)

(Sure VCS was kind of a technological revolution, so if possible, let's keep the answers in computer science theory and not the applications in software engineering)

PS: I could not really find a suitable tag :-(

# Answer
> 2 votes
Computer science is, at its core, the study of algorithms. What can we compute, and how fast can we compute it? Its sub-fields, such as image processing, AI, Operating Systems, Programming Languages, numerical computing, etc. can be viewed as answering these questions for specific types of problems.

With that in mind, I think the most major revolution is:

**Godel/Turing and Undecidability**

The mathematician Hilbert posed a series of problems to the mathematical community. One was to find an algorithm for the *Decision problem*: that is, to look at any theorem, and state whether it was true or false.

In different ways, Godel and Turing each proved that this was impossible. This revolutionized the way we thought about computation, because for the first time, we had a definitive proof that something could *not* be computed. No amount of human cleverness could completely solve the problem.

Directly related to this, Turing Machines and the Church-Turing thesis were developed. This formalized what it *meant* to compute, turned algorithms from things humans talked about into mathematical objects that could be reasoned about, have theorems proved about them. And it established that the two extreme ways of thinking of computation, namely as functions and as transformation of an infinite memory, were equivalent.

# Answer
> 1 votes
I'm very unsure of what are you asking, but here is an answer based on a purely subjective take on your "question":

Here's Moore's law:

> The complexity for minimum component costs has increased at a rate of roughly a factor of two per year. Certainly over the short term this rate can be expected to continue, if not to increase. Over the longer term, the rate of increase is a bit more uncertain, although there is no reason to believe it will not remain nearly constant for at least 10 years.

Long story short, it states that **the overall processing power of computers doubles every two years**.

This has been held true in the past, due to certain hardware advancements such as the silicon chip, but the last 10 - 15 years have started to prove it wrong. Optimizing infrastructure is getting harder and harder. First of all because it has to be quasi - compatible with the old infrastructure. Second, because it has to be better.

Quantum Computing and Engineering is most likely to provide new and better machines in the future. The "revolution" has not yet taken place because constructing compact quantum computers is far from easy. The smallest and fastest quantum computers are currently being produced by D - Wave (coming up second is IBM, I believe). Even though the first quantum computers are not as "fat" as their digital brothers, such as ENIAC, they still occupy to much space to become household items.

Research in quantum computing is still being done. There new quantum algorithms, with much, much better time **and** space complexity than the classical ones. Here's just a few: Simon's algorithm, Shor's algorithm, Grover's algorithm and the list goes on. When it comes to algorithm optimization, progress is surely being made.

Overall, the only thing speeding down this "quantum computing revolution" (apart from the tendency of most programmers to stick to languages and software that has already been used for a while) is the fact that quantum computers are still to big to fit in a home. And expensive. Laptops and smartphones are, of course, out of the question for the time being.

---
Tags: software-engineering
---


# Question
Title: Solving functional equations for unknown functions in lambda calculus
Are there any techniques for solving functional equations for unknown functions in lambda calculus?

Suppose I have the identity function defined extensionally as such:

$I x = x$

(that is, by writing down an equation for the expected behaviour of that function) and now I want to solve it for $I$ by doing some algebraical transformation to get the intensional formula for that function:

$I = \lambda x.x$

that tells *how exactly* does the function do what was expected (that is, how to implement it in lambda calculus).

Of course the identity function is used just as an example. I'm interested in more general methods of solving such equations. In particular, I would like to find a function $B$ that satisfies the following requirement:

$B\\;f\\;(\lambda x.M) = (\lambda x.f M)$

that is, "injects" the given function $f$ into the given lambda function $(\lambda x.M)$ before its "body" $M$ (which is some arbitrary lambda expression), possibly by taking it apart and constructing a new one, so that it became a parameter the function $f$ is applied to.

# Answer
> 13 votes
This is a known problem, known as Higher Order Unification.

Unfortunately, this problem is undecidable in general. There is a decidable fragment, known as Miller's Pattern Fragment. It's used extensively in, among other things, typechecking of dependently-typed programs with metavariables or pattern matching. This fragment is where unification variables are applied only to distinct bound program variables.

This paper provides a great tutorial of how higher order unification works, and walks through a (relatively) simple implementation of it.

Unfortunately, it doesn't look like your function falls into this pattern fragment. That said, what I'm looking seeing is pretty similar to function composition. Does the following function satisfy your property?

$B = \lambda f\ g\ x\ \ldotp f\ (g\ x) $

We have:

* $B\ f\ (\lambda x . M)$
* $= B\ f\ (\lambda y . \[y/x\]M)$ by $\alpha$-equivalence
* $ = \lambda x . f\ ((\lambda y. \[y/x\]M) x) $
* $= \lambda x . f\ (\[x/y\]\[y/x\]M)$
* $= \lambda x . f\ M$

# Answer
> 2 votes
I think I have a partial answer, regarding the equation with the identity function:

$I x = x$

We want to solve it by finding the formula for $I$, which will be of the form $(\lambda p.M)$ with some yet unknown expression $M$ as its body. Let's substitute it for $I$ in the original equation:

$(\lambda p.M)\\; x = x$

then apply the function to $x$ on the left hand side:

$M\[p/x\] = x$

But what do we have here? :\> This equation is the formula for the expression $M$ we're looking for, after substituting every occurrence of $p$ in it with $x$, and it says that it should look like the right hand side afterwards :) In other words, the function we were looking for is:

$I = (\lambda x.x)$

which of course is the right answer :)

---

Let's try the same approach to find the formula for the $\omega$ combinator. We want it to work in such a way that, when applied to itself, will produce itself applied to itself:

$\omega\\;\omega = \omega\\;\omega$

Now let's find the formula for $\omega$ which is of the form $(\lambda x.M)$ for some yet unknown expression $M$. Substituting this into the equation we get:

$(\lambda x.M)\\;\omega = \omega\\;\omega$

Applying it to the parameter on the left hand side gives the formula for $M$:

$M \[x/\omega\] = \omega\\;\omega$

This says that after substituting every occurrence of $x$ in $M$ with $\omega$ it produced $\omega\\;\omega$, so we can deduce that the original expression $M$ before substitution should have been $x\\;x$, so the function we were looking for should look like this:

$\omega = (\lambda x.x\\;x)$

which is indeed the case :)

---

I have a feeling, though, that it might get so easy just because the right hand side was already in the form we're looking for.

---
Tags: lambda-calculus
---


# Question
Title: Is final state mandatory in DFA(Deterministic Finite Automata)
In state diagram of DFA is it mandatory to keep a final state. I mean whether DFA is possible without final state or not?!

# Answer
The definition of DFAs calls for a set of final (aka accepting) states. Nothing requires that set to be non-empty. But note that a DFA without an accepting states can't accept any input, so all such DFAs are essentially equivalent to the one you drew.

Having said that, the class of languages accepted by DFAs wouldn't change if you insisted that every DFA must have at least one accepting state. You could still accept the empty language with an automaton whose state graph was disconnected, with all accepting states unreachable from the initial state. If you insisted on at least one accepting state *and* a connected state graph, the empty language wouldn't be accepted by any DFA.
> 6 votes

---
Tags: automata, finite-automata
---


# Question
Title: traverse direct graph with multiplicative edges
I have a graph like this one:

Each step from one node to another is a multiplication.

So for instance given the entry node TE and an entry value of 1.

TE = 1

TB = 1/10010

GB = 999/(10010\*1000)

GE = (19990\*999)/(10010\*1000)

and so on.

I want to find the best path from TE to TE to return the highest value.

In this case is

TE TB GB GE TE = 1,993010988

I tried to apply Dijkstra's SPF but it doesn't work because each step can increment or decrement so it's not monotone

neither Bellman–Ford algorithm is applicable here because the graph contains negative cycle. (e.g. TE TB TE).

Anyone has some clue if this problem has a solution ?

# Answer
The fact that the weights are multiplicative is essentially irrelevant – you can always take logs, add the logs, then exponentiate. However, looking for the shortest simple path (i.e., no repeated vertices, so you're not whizzing round negative cycles) is an **NP**-hard problem when there are negative-weight cycles, as explained by Danny Pflughoeft on CS Theory SE. Essentially, longest path in a graph where all weights are non-negative becomes shortest path if you negate all the edge weights, but Hamiltonian path reduces easily to longest path.

You're now allowed to complain that I'm a complexity theorist, since you asked for an algorithm and I said "There's no fast one" as if that was the complete answer.

Wait, now I'm allowed to complain. You tagged your question "shortest-path" but you're actually looking for longest paths. That's straight-up **NP**-hard. Just give every edge weight $2$ and the longest simple path has weight $2^n$ if, and only if, the graph has a Hamiltonian cycle.
> 3 votes

---
Tags: graphs
---


title: NEXP = Σ$_2$ ⟹ NEXP = MA?

text:
# Question
Title: NEXP = Σ$_2$ ⟹ NEXP = MA?
Is it known whether the implication $\mathsf{NEXP} = \Sigma\_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds?

(The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} \Leftrightarrow \mathsf{NEXP} = \mathsf{MA}$.)

# Answer
This is not known.

$NEXP = \Sigma\_{2}$ means that $NP$ and $NP^{NP}$ are different. But, $MA$ seems too weak to reach that high to catch $NP^{NP}$.
> 1 votes

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


title: On lowness of $\oplus P$

text:
# Question
Title: On lowness of $\oplus P$
$\oplus P$ is low for itself ($\oplus P^{\oplus P}=\oplus P$).

1. Are there other complexity classes $\mathcal D$ that satisfy $\mathcal D^{\oplus P}=\oplus P$?
2. Are there complexity classes $\mathcal C$ that satisfy $\mathcal C^{\oplus P}=\mathcal C$?

# Answer
> 1 votes
Weak complexity classes will satisfy $\mathcal{D}^{\oplus P} = \oplus P$. For example, $P^{\oplus P} = \oplus P$.

Strong complexity classes will satisfy $\mathcal{C}^{\oplus P} = \mathcal{C}$. For example, $\mathsf{PSPACE}^{\oplus P} = \mathsf{PSPACE}$.

---
Tags: complexity-theory, time-complexity, complexity-classes, polynomial-time, counting
---


# Question
Title: Why selection sort will require $O(N)$ time
As per the example given in this MIT OCW link URL https://ocw.mit.edu/courses/civil-and-environmental-engineering/1-124j-foundations-of-software-engineering-fall-2000/lecture-notes/sorting/

Why selection sort requires $O(N)$ time since the number of exchanges is at most N. Pls give example algorithm that prove this fact. Below is excerpt taken from same MIT OCW URL for reference

Selection sort is easy to implement; there is little that can go wrong with it. However, the method requires $O(N^2)$ comparisons and so it should only be used on small files. There is an important exception to this rule. When sorting files with large records and small keys, the cost of exchanging records controls the running time. In such cases, **selection sort requires $O(N)$ time since the number of exchanges is at most $N$.**

# Answer
> 3 votes
It is simpler and more correct to say: selection sort requires $O(n)$ exchanges (and this is optimal in the worst case).

That doesn't imply $O(n)$ time, unless the other operations take negligible time. But from a theoretical standpoint, $O(n^2)$ is *never* negligible compared to $O(n)$.

In practice if a comparisons and related overhead takes $s$ seconds and an exchange and related overhead takes $e$ seconds, the total time will be

$$\frac{sn^2}2+cn=\left(\frac{sn}2+c\right)n.$$

This can be considered a linear behavior as long as $sn\ll c$. That could be true if the records are stored on a slow disk while the keys are cached in RAM.

---

This course plays a dangerous game with the Big-$O$ notation.

# Answer
> 0 votes
Suppose that the cost for comparing two keys is $A$ and that the cost for exchanging two records is $B$. Then the running time of selection sort is $$ O(An^2 + Bn). $$ If $A$ is much smaller than $B$ (by a factor of $\Omega(n)$), then the second term is dominant.

---
Tags: algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: Algorithm for finding cycles in a hypergraph
Define a hypergraph as a set $V$ of vertices and a set $E$ of hyperedges, where a hyperedge is a non-empty subset of $V$. (This is a generalisation of an undirected graph, in which edges are allowed to connect any number of nodes, rather than just two.)

Define a cycle in a hypergraph as a cyclic sequence $C$ of vertices $v\_0,v\_1,\dots,v\_n,v\_0$, such that

(i) there is no hyperedge that includes all of the members of $C$; and

(ii) for every adjacent pair of vertices in $C$, there is a hyperedge that includes them both.

I'm looking for a simple and straightforward algorithm to detect whether any given hypergraph has a cycle. I feel like it should be obvious but it's not coming to me.

In case it helps: the hypergraphs I'm dealing with are reduced (meaning that no hyperedge is a subset of any other hyperedge), and also have the property that there is at least one hyperedge that contains each vertex.

# Answer
> 2 votes
Yes, there is a simple and efficient algorithm for this.

Given a hypergraph $H=(V,E)$, construct an undirected graph $G$ as follows: add the edge $(u,v)$ to $G$ if there is a hyperedge that contains both $u$ and $v$. Find the connected components of $G$.

Your condition (ii) is now equivalent to: $v\_0,v\_1,\dots,v\_n$ are all in the same connected component. Thus, you want to find a subset of vertices that are all in the same connected component, but aren't contained in any hyperedge.

This leads to a simple algorithm. Iterate over the connected components of $G$. Let $S$ denote the set of vertices in one connected component of $G$. Test whether $S$ is contained in any hyperedge of $H$. If it isn't, then the hypergraph has a cycle (any cycle in $G$ that visits each vertex of $S$ at least once, and doesn't visit any vertex outside $S$, is a cycle in $H$). If after testing all the connected components of $G$, none of them are a valid cycle, then the hypergraph doesn't have any cycles.

(You don't need to test any of the subsets of $S$. If $S$ isn't a cycle, then none of the subsets will form a cycle, either. Why? If $S$ violates condition (i), then every subset of $S$ will violate condition (i), too.)

---
Tags: algorithms, graphs
---


# Question
Title: Neural network to detect connected parameters
I have a list of configurations. Each configuration contains a number of parameters. The parameters have the same name but sometimes different values. I now want a neural network, that can detect, which Parameters always have the same value when Parameter 1 has value 'A'.
I want to find out which Parameters are "related", so which parameters always change together and have always the same pair of values.

# Answer
That's easy. Find all configurations where parameter 1 has value A; throw away all the rest. Now you can easily test whether all the remaining parameters have the same value for parameter 2 (just scan through them and see if they all have the same value as the first); you can do that for parameter 3; and so on. No fancy algorithm is needed -- it's straightforward to program with a simple linear scan.
> 1 votes

---
Tags: neural-networks
---


# Question
Title: Theorem Prover for complexity theoretic reductions
Can complexity theoretic reductions that lead to proofs of say NP completeness be formalized using an existing theorem prover such as Coq?

If so, can you provide an outline of how to formalize a simple reduction argument? I’d also appreciate pointers to the literature.

# Answer
> 5 votes
This is certainly possible, and the language of higher order functions makes this quite nice. If you're doing a Turing/Cook reduction, you can basically just write a function that takes an oracle as a parameter.

For example, to show that Graph Coloring is NP-hard, you could write something like this (pardon my terrible Coq-like pseudocode)

```
Theorem reduction:
  (forall (k:Nat) (g:Graph), Decidable (Coloring g))
  -> (forall (f:BoolFormula), Decidable (Model f))

```

What gets tricky is proving that your reductions are polynomial-time. There are ways to do this, such as with a time-tracking monad. This example verifies the time complexity of a sorting algorithm, and gives some hints as to how to model this. Basically, for whatever operation you're counting as $O(1)$, you require that it be performed in the monad, as well as calls to your oracle. Then you write a proof of some polynomial bound on the number of operations performed in the monad (which can keep track of them by encapsulating state).

---
Tags: complexity-theory, automated-theorem-proving
---


title: Learning Automated Theorem Proving

text:
# Question
Title: Learning Automated Theorem Proving
*I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here.*

*Note that these topics are not easily digested without a background in (mathematical) logics. If you have problems with basic terms, please read up on those, for instance Logics in Computer Science by M. Huth and M. Ryan (in particular chapters one, two and four) or An Introduction to Mathematical Logic and Type Theory by P. Andrews.*
*For a short introduction into higher order logic (HOL) see here.*

I looked at Coq and read the first chapter of the intoduction to Isabelle amongst others; Types of Automated Theorem Provers

I have known Prolog for a few decades and am now learning F#, so ML, O'Caml and LISP are a bonus. Haskell is a different beast.

I have the following books

"Handbook of Automated Reasoning" edited by Alan Robinson and Andrei Vornkov

"Handbook of Practical Logic and Automated Reasoning" by John Harrison

"Term Rewriting and All That" by Franz Baader and Tobias Nipkow

1. What are the differences between Coq and Isabelle?
2. Should I learn either Isabelle or Coq, or both?
3. Is there an advantage to learning either Isabelle or Coq first?

*Find the series' next question here.*

# Answer
My preference is for Coq, but I imagine that others prefer Isabelle. One of the strange things I found about Isabelle is that there is a two-level syntax, where some of your definitions need to be inside double quote. No such nonsense is present in Coq.

Ultimately, the one that is most suitable for you may depend on what you want to prove. Both languages have a lot of library support and active communities doing all sorts of development and example theories. If one language provides adequate library (or other) support for the kinds of theory you wish to develop, then I'd select that language.

One strategy is to do a simple tutorial in both languages and follow up the one that feels the best. For example,

Here is a blog post briefly comparing the two by someone who ultimately prefers Isabelle.

Make sure you use a proper IDE (such as ProofGeneral), rather than doing things on the command line.

Another way to to get into Coq is to try the online book Software Foundations by Benjamin Pierce et al. It provides an excellent tutorial with loads of details provided. The focus is mostly on programming language semantics, but a lot of the basics (and beyond) of Coq and semi-automated theorem proving are covered along the way.
> 25 votes

# Answer
One thing that I think you'll find interesting is that the "theorem proving" term varies vastly depending on what field you're in. While they are -- in the abstract -- somewhat related, practical theorem proving (like the kind you see elaborated on in the Handbook of Automated Reasoning) has less to do with Coq or Isabelle than you would think.

When I first set out to learn about theorem proving related things, the first book I read (although now quite dated?) was Melvin Fitting's excellent First Order Logic and Automated Theorem Proving. This book was a really excellent one that covered the kinds of topics you'll see that relate to the lower order logics, where you can actually get a fair amount of automation. The kind of logic you learn should be dictated by what you want to reason about, and not so much theorem proving for the sake of it. For example, while first order logic gives you a fair amount of expressiveness and reasoning ability, most of the programming languages community (where I've ended up these days) has departed from the older school of theorem proving and model checking (which go into the bucket of things which are more decidable but less expressive).

*Don't* take this to mean -- however -- that things like first order reasoning and model checking haven't been extremely useful in practice. They have been! You can look at ACL2 as an example of a prover built atop first order logic which has sen an amazing amount of success in the industrial realm. Along with that, there has also been an amazing amount of development in SMT solving. Modern SMT solvers are built on top of very powerful SAT solvers (mostly through discoveries within the last twenty years for improvements on DPLL), and have seen a great amount of use in things like symbolic execution.

However, as I said, while the more traditional "theorem proving" bit is fun, there's a *lot* more to learn. Learning Coq -- for example -- has little to do about learning the automation tools it gives you, and has a lot more to do with learning the type theory upon which it's based (the predicative calculus of coinductive constructions). If you're not used to constructive logic, the curry howard isomorphism, or type theory, you'll have an exciting time learning these tools, but I can hardly think that they're too closely related to things you see in the first volume of the handbook.

So decide what you want to do: verify models and theorems in first order logic, or use a powerful type theory to reason about correctness of your programs (or theorems in constructive logic). If it's the first, learn about more automated deduction based techniques, if it's the second, learn more about Coq, HOL, etc... By the way, if you want to learn Coq, while the above references are good, I think that there are two really core references for learning Coq:

Benjamin Pierce's software foundations book (Dr. Pierce is an excellent writer, and I'd recommend you also look at his more popular "brick book," if you haven't yet).

Certified Programming with Dependent Types (Adam Chlipala also writes quite well, though his books assume a bit more maturity and intelligence than Pierce's perhaps simpler introduction.)
> 19 votes

# Answer
There is a variety of systems for Interactive Theorem Proving (ITP) -- see also the conference of that name -- Coq, Isabelle, HOLs, ACL2, PVS etc.

All of them are relatively challenging to learn, and each has its own specific culture. It is like learning a foreign language: lets say you know English already, and then have the choice of French, German, Italian, Spanish, Portuguese. All of them are somehow related -- this is not Chinese -- but very few people manage all of that simultaneously. So you should try get a taste for each of the cultures and communities, and then make a commitment.

There might be also the "killer feature" that you really need for your work.

It also helps to have fellow experts on one of these systems around.

* *What are the differences between Coq and Isabelle?*

Both are descendants of the LCF system from Stanford/Edinburgh/Cambridge. In 1985, G. Huet and L. Paulson were working together on the last version of Cambridge LCF. Then the split happened towards Coc/CIC/COQ (now Coq) in France, and Isabelle in Cambridge and Munich. Note that HOL4, HOL-Light, HOL-XYZ are other related descendants of LCF.

More than 20 years ago, the distinction of Coq vs. Isabelle would have been made according to logical foundations: Dependently Typed Constructive Logic here, Simpl-Typed Classical Logic there. Today, there is surprisingly little impact on that in practice, since more and more layers have been added on top of each formal system, including add-on tools, and libraries.

* *Should I learn either Isabelle or Coq, or both?*

You should *look* at both, and try to get a feeling if you like more Wine and Cheese, or Bratwurst and Sauerkraut. (As one of the guys behind Isabelle, but presently at France, I am surprised how many Frenchmen actually like Sauerkraut when they are privately at home and nobody looking :-)

* *Is there an advantage to learning either Isabelle or Coq first?*

I don't think so. There might be a danger that you get stuck with the one you try first and don't try the second, or that you get disappointed too early with the first and dismiss it too early. In any case, you will need time and persistence to become productive with either system.

Since Proof General as "IDE" was mentioned already: Proof General / Emacs used to be the standard unifying interface for both Coq and Isabelle over many years, but I would never have called it an IDE. There is also CoqIDE with "IDE" in its name, but is a relatively basic editor on top of Gtk widgets. Current Isabelle includes Isabelle/jEdit, which does not have "IDE" in its name, but is meant to approximate things you see routinely in Netbeans or IntelliJ IDEA --- for proof texts instead of Java code.
> 15 votes

# Answer
Here are some nice video Coq tutorials by Andrej Bauer. It's in no way complete, but I think it's a good introduction.
> 10 votes

# Answer
This introduction to Isabelle is pretty exhaustive.

Also see this introduction to Isabelle

In general, Isabelle is relatively easy to start with, as there are many available examples. For example, in the official website

P.S - I am in no way affiliated with Isabelle, I'm a theoretician in formal methods, but I know Isabelle comes up often as a default starting point.
> 4 votes

# Answer
I've recently came to these Coq tutorials from $\lambda$conf2017 so I've figured out it's worth sharing here for whoever visits this question later.

Also, DeepSpec Summer School's Software Foundations has some pretty cool lectures:

Some of the lectures based on the Software foundations series, that was already mentioned.
> 2 votes

---
Tags: logic, proof-assistants, automated-theorem-proving, coq
---


# Question
Title: How to calculate least common multiple (LCM) for two numbers with constants (shifts)?
What's the most effective algorithm to calculate LCM for 2 numbers where each of them has their own "shift"?

Example:

We want to find LCM for 25 + 5 as c and 30 + 10 as c Then for the first case, the sequence will look like this:

25\*1+5, 25\*2+5, 25\*3+5, 25\*4+5...

And the second one:

30\*1+10, 30\*2+10, 30\*3+10, 30\*4+10...

In this case, the result should be 130 - 5th member of the first sequence and 4th of the second one.

# Answer
> 0 votes
Given integers $a,b \geq 1$ and $c,d \geq 0$, you are looking for the set of solutions of $ax + c = by + d$ over integers $x,y \geq 0$. We can assume without loss of generality that $d = 0$ (replace $c,d$ with $c-d,0$ or $0,d-c$) and that $(a,b,c) = 1$ (otherwise, divide everything by the GCD).

I claim that if there is any solution then necessarily $(a,b) = 1$. Indeed, suppose that $(a,b) = g \> 1$. If $ax + c = by$ then $g \mid ax,by$ implies $g \mid c$, and so $(a,b,c) = g \> 1$, contrary to assumption. Therefore $(a,b) = 1$.

If $ax + c = by$ then $ax + c \equiv 0 \pmod{b}$ and so $x \equiv -c/a \pmod{b}$ (note that we can divide by $a$ since $(a,b)=1$). Similarly, $y \equiv c/b \pmod{a}$. These equations essentially give us both the minimal solution and all solutions.

As a demonstration, consider your example: $30x+10 = 25y+5$. This is equivalent to $6x+1 = 5y$, so $(a,b,c) = (6,5,1)$. Any solution must satisfy $x \equiv -1/6 \equiv 4 \pmod{5}$ and $y \equiv 1/5 \equiv 5 \pmod{6}$. Indeed, $6 \cdot 4 + 1 = 5 \cdot 5$. The general solution is $(x,y) = (4+5N,5+6N)$.

---
Tags: algorithms
---


title: Low for EXP and NEXP

text:
# Question
Title: Low for EXP and NEXP
What are the largest classes which are low for EXP and NEXP?

For example: I am aware the class P, QP are low for EXP as well as NEXP. We also know that NP is not low for either of them.

Is class BPP low for EXP or NEXP? What is the largest oracle class we can provide to EXP (or NEXP) which doesn't increase its power?

# Answer
> 2 votes
$\mathsf{BPP=NEXP}$ is consistent with our current knowledge, thus, since $\mathsf{EXP, NEXP}$ are not low for themselves, it is not known whether $\mathsf{BPP}$ is low for them. A positive answer would imply $\mathsf{BPP\neq NEXP}$, and a negative answer would imply $\mathsf{P\neq BPP}$ (and in turn, that $\mathsf{P\neq NP}$), so currently, if you're looking for unconditional results, you will have no luck with $\mathsf{BPP}$.

Since even a (possibly weak) class as $\mathsf{BPP}$ is not known to be low for $\mathsf{EXP}$, you will need to look between $\mathsf{P}$ and $\mathsf{BPP}$ (which does not give you much wiggle room), or for classes who are currently incomparable with $\mathsf{BPP}$ (such as $\mathsf{QP}$ as you yourself noted, I doubt you can find a significantly stronger low class for EXP).

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


# Question
Title: Is there an online algorithm for radix conversion?
Suppose I have $P$, which is the base-$p$ representation of an integer $n$ and I want to calculate it base-$q$ representation $Q$. The obvious algorithm is: interpret $P$ to obtain $n$, then calculate $Q$ from $n$. This is easy.

But if $n$ is very large this could require a lot of memory, and it could require a large amount of processing before any of the digits of $Q$ are emitted. In certain special cases we can do better; there is an online algorithm which can start producing output before all the input is read. For example, if $p^i = q^j$ then the algorithm can read $i$ digits of $P$ and immediately produce $j$ digits of $Q$ without any further input and with only a constant amount of memory. This method is used, for example, in converting generic computer data ($p=256$) to “Base64” format ($q=64$).

Is there a general online algorithm for radix conversion? I expect that if there is such an algorithm, in the worst case it cannot emit any digits of $Q$ without first reading all of $P$, but are there algorithms that can often do better than this, in cases more general than the very unusual $p^i=q^j$ situation? Or are there any other special cases of interest?

\[ Related thread: The math behind converting from any base to any base without going through base 10? but all of the suggestions there ingest the entire input before producing any output. \]

# Answer
> 1 votes
This answer is not complete, but it is the start of a complete answer, and nothing else has been offered. I hope to finish it another time.

I have found that an online right-to-left algorithm exists in a more general case than I mentioned in my original question.

---

I suspect that no such algorithm exists in general, for reasons I outlined in my comment. What would the online algorithm produce first?

### Units digit first

Suppose the algorithm wants to produce the units digit of $Q$ without reading all of $P$. Represent $n$ in base-$p$ as $n = \sum\_i d\_ip^i$ where each base-$p$ digit $d\_i$ is between $0$ and $p-1$ inclusive. The units digit of $Q$ is equal to $n\bmod q$ which is $$\Bigl(\sum\_i d\_ip^i\Bigr)\bmod q.\tag{$\star$}$$ The result depends on every one of the $d\_i$ unless the corresponding term $d\_ip^i$ has the same value $\bmod q$ for each possible value of $d\_i$. In particular we must have $$0\cdot p^i \equiv 1\cdot p^i\pmod q$$ so $p^i$ must be a multiple of $q$ in order for us to ignore the $i$th term of the sum. Say $p^{k\_0}$ is a multiple of $q$ for some $k\_0$. Then in computing the units digit of $Q$ we can disregard all the terms of the sum with $i\ge k\_0$, and we need only examine the first $k\_0$ digits of $P$.

To compute the next digit of $Q$ we can disregard all the terms of the sum with $i\ge k\_1$ where $k\_1$ is the smallest number for which $p^{k\_1}$ is a multiple of $q^2$, and so on.

For example, suppose $p=6$ and $q=8$ and $n=3021213\_6$. $6^3$ is a multiple of $8$ so we can generate the units digit of $Q$ just by examining the last three digits of $P$. $2\cdot6^2 + 1\cdot 6 +3 \equiv 1\pmod 8$ so the units digit of $Q$ is `1`. Reading the next three digits of $P$ will allow us to compute another digit of $Q$, and so on.

This situation includes the case of $p^i=q^j$ that I discussed in the original question, but it is more general.

Note that although the $k\_i = O(i)$ it may not increase smoothly. We actually have $k\_i = \lfloor c(i+1)\rfloor$ for some rational constant $c$ that depends on $P$ and $Q$. For example, $24$ is a multiple of $4$, and so $24^2$ must be a multiple of $4^2$, but it is also a multiple of $4^3$. Next $24^3$ is a multiple of $4^4$ but not of $4^5$. So when converting from base $24$ to base $4$, reading the first digit of $P$ gets you one digit of $Q$, but reading the next digit of $P$ gets you not one but two more digits of $Q$. Reading the third digit of $P$ gets you only one more digit of $Q$. Here $c = \frac32$.

---

(To come: most significant digit first; intermediate digits first.)

---
Tags: number-theory, online-algorithms, base-conversion
---


# Question
Title: What is the fastest known algorithm for matrix multiplication as of (2017/11)?
Recently I have learned about both the Strassen algorithm and the Coppersmith–Winograd algorithm (independently), according to the material I've used the latter is the "*asymptotically fastest known matrix multiplication algorithm until 2010*". As It can multiply two ( n * n) matrices in 0(n^2.375477) time.

As of now (2017/11) I wish to know, is there another algorithm for matrix manipulation that was discovered since then (2010)?

I kind of knew in the CS field (I know I should probably do further research myself).

# Answer
> 3 votes
If you read the Wikipedia article you link to, it already describes improvements to the algorithms: "In 2010, Andrew Stothers gave an improvement..." and "In 2011, Virginia Williams ..." and "In 2014, François Le Gall ...". The latter is the best currently known algorithm.

To make this answer useful in the future: to verify whether this is still true or whether there is some further improvement, go enter those paper citations into Google Scholar and look at the papers that cite them. If there were any improvements, the improvement would be published and would cite those papers.

---
Tags: algorithms, complexity-theory, time-complexity, matrices
---


# Question
Title: Confusion about reduction of $L=\{w_i | M_i\text{ halts on }w_i\}$ to Halting Problem or Diagonalization language?
I want to reduce $L$ (stated above) to the Halting Problem in order to say that L is recursively enumerable but not recursive just like the Halting Problem, but is it enough to say that if I can solve the Halting Problem then I can solve $L$, because then I can feed into the Halting Problem the input $w\_i$ twice, as both input and Turing machine encoding?

Do I need to reduce it to the diagonalization language instead?

# Answer
> I want to reduce $L$ (stated above) to the Halting Problem in order to say that L is recursively enumerable

So far, so good.

> but not recursive just like the Halting Problem

Here we have a problem. Reducing $L \leq\_m HALT$ does not prove that $L$ is not recursive. Actually, all recursive languages reduce to $HALT$!

> but is it enough to say that if I can solve the Halting Problem then I can solve $L$

No, this is not a may-one reduction argument. Indeed, if you can solve $HALT$, then you can also solve its complement. This however, does not imply that the complement is r.e., otherwise we would get that $HALT$ is recursive.

You need to define a (total recursive) reduction function from $L$ to $HALT$.

Then you need to prove that $L$ is not recursive. For that, you could prove the opposite direction $HALT \leq\_m L$, constructing a reduction function from $HALT$ to $L$.
> 0 votes

---
Tags: computability, reductions, halting-problem
---


# Question
Title: Proving Blank-halt to be recursively enumerable through reduction to Halting problem
To prove the blank-halt problem is undecidable (does a given Turing machine halt on the empty input), it's a case of reducing the halting problem to the blank-halt problem and since the halting problem is undecidable, the blank-halt problem is undecidable.

However to prove the blank-halt problem is recursively enumerable just like the Halting problem, isn't the reduction then the other way around? In order to prove this part does the blank-halt problem get reduced to the halting problem and so if the halting problem is recursively enumerable then the blank halt problem is also recursively enumerable?

I'm confused about the reduction flow.

# Answer
> 1 votes
If you reduce $X$ to $Y$, you're showing that $X$ is no harder than $Y$ and that $Y$ is at least as hard as $X$.

So, by showing that some problem $X$ reduces to the halting problem, you're showing that $X$ is no harder than the halting problem, i.e., that it's recursively enumerable. Remember that we normally define problem classes to include all lower classes, so showing that $X$ is RE doesn't necessarily imply that it's not recursive, for example. In this case, we can separately prove that the blank halting problem isn't recursive, by reducing the halting problem *to* it, which shows it's at least as hard as the halting problem, as above.

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


title: Does the empty word count as a 'word'?

text:
# Question
Title: Does the empty word count as a 'word'?
If I have DFA accepting

$\\{w \in \\{a,b\\}^\*$ s.t. on every odd position in $w$ there is a $b\\}$

Would the empty word be accepted? Also, would the word $eb$ be accepted?

# Answer
> 1 votes
The empty word belongs to the language, since on all its odd positions -- all zero of them -- we find a $b$.

$eb$ does not belong to $\\{a,b\\}^\*$, hence it does not belong to the language.

---
Tags: finite-automata
---


# Question
Title: What is the minimal pumping length of this string $(01)^*$
In this answer, it is told that the minimal $p$ value is $1$. One of the conditions of the pumping lemma is that

$|xy| \leq p$

Now if we try to split a string $01^p$, we might do it like this:

$x=\epsilon$, $y=01$, $z=01^{p-1}$

But this decomposition contradicts the above condition. If we arrive at a contradiction, then how $p$ can be equal $1$?

Besides, is there a maximum pumping length? Various sources define $p$ as constant, and if it is a constant, there should be a single value instead of minimum and maximum range.

# Answer
The pumping length of a regular language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be split as $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) $xy^iz \in L$ for every $i \geq 0$. The pumping length of $(01)^\*$ using this definition is $2$. Anybody claiming that the pumping length is $1$ is either wrong or has a different definition in mind (the notion of pumping length isn't completely standard, and my definition is not the only possible one).

In order to show that the pumping length cannot be $1$, you need to show that there exists some word $w \in L$ of length at least $1$ such that for every splitting $w = xyz$ in which $|xy| \leq 1$ and $y \neq \epsilon$ there exists $i$ such that $xy^iz \notin L$. In particular, you *don't* get to pick the decomposition. You need to show that *no* decomposition works. In this case, we can take the word $w = 01 \in L$. Since all words in $L$ have even length, if $w = xyz$ and $xz \in L$ then necessarily $y$ has even length. However, this is impossible since on the one hand $|y| \leq |xy| \leq 1$, and on the other hand $y \neq \epsilon$.
> 6 votes

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


# Question
Title: Clarification on Solving Recurrence Relations (Linear)
I'm trying to understand how to find the asymptotic complexity of a linear recurrence relation. So far, what I understand is that if only one linear recurrence call is made (ex. cn + T(n-4)), substitution or the recurrence tree can be used. However, what should one do if there are 2 or more linear recurrence calls? For the example I got in class (shown below), I got that T(n) = T(n-4) + logn + T(n-10). I tried setting a lower bound of T(n)\> log n + 2T(n-10) since that's how we solved Fibbonacci Numbers, but I wound up with a complex summation that I could not solve. Any help is appreciated, thank you!

# Answer
> 0 votes
The first step is to solve the easier recurrence $$ T(n) = T(n-4) + T(n-10). $$ This is explained in our reference question. The solution to your recurrence will likely be larger by a factor of $\log n$, roughly speaking.

Indeed, you can consider a recursion tree in which the root is $n$, and a node $m$ has children $m-4$ and $m-10$ (you stop the recursion at some constant $m$). The solution to the recurrence $T(n) = T(n-4) + T(n-10)$ is proportional to the number of leaves, which we expect to be proportional to the number of nodes. For all $m \geq \sqrt{n}$ (say), $\log n = \Theta(\log m)$, which leads us to expect that the solution of your non-homogeneous recurrence is larger by a factor of $\log n$ than the solution of the corresponding homogeneous recurrence $T(n) = T(n-4) + T(n-10)$.

The preceding paragraph contains some intuition which will need to be proven. But whether or not the $\log n$ factor appears in the final formula makes little difference, since the growth rate of the recurrence is exponential.

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP?
The following theorem (from "The Design of approximation algorithms" by Williamson & Shmoys, pg 43) states:

> For any $\alpha \> 1$, there does not exist an $\alpha$-approximation algorithm for the traveling salesman problem on $n$ cities, provided $P \neq NP$. In fact, the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$.

This theorem is given without a proof. It only explains, before the theorem formally stated, that for any $\alpha \> 1$, there does not exist an $\alpha$-approximation algorithm. This part is clear. But the claim that *the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$* is not obvious to me. Could someone give me a hint how to prove it or sketch of proof?

# Answer
After @YuvalFilmus' hint it turns out the answer lies in this book. The TSP can be used to solve the Hamiltonian Cycle problem by creating a new graph as following. Given $\alpha \> 1$ and a graph $G=\langle V,E \rangle$ we create a new graph $G'=\langle V',E' \rangle$ such that $w(e')= 1$ if $e\in E$, and $w(e')= \alpha n+2$ if $e\notin E$. If $G$ has a Hamiltonian cycle then $G'$ has a tour of length $n$, otherwise each tour has length is at least $(\alpha+1)n + 1$.

Now we run $\alpha$-approximation algorithm for TSP and if the tour computed has cost at most $(\alpha+1)n$ then there is a Hamiltonian cycle in $G$, otherwise there doesn't. If we set $\alpha = O(2^n)$ then we have $O(2^n)$-approximation algorithm. This algorithm runs in $O(f(2^n))$ time for some polynomial $f$, but its time complexity is still polynomial in length of input. This means we would solve the Hamiltonian Cycle problem in polynomial time implying $P=NP$.
> 4 votes

---
Tags: algorithms, complexity-theory, approximation, traveling-salesman
---


# Question
Title: Is the language $\{ 0^m 0^n : 0 \leq m \leq n\}$ regular?
> Is the following language regular? $$ \\{ 0^m0^n : 0\le m\le n \\}. $$

According to me, it is not regular. However, some of my friends are arguing that every string in $0^\*$ can be divided into $0^m0^n$ satisfying the constrains between $m$ and $n$, hence it is regular.

Although I am absolutely sure that their reasoning is false, they are thinking in reverse, I would like a third opinion.

Here is my proof of non-regularity:

Let us take $0^p0^{p+1}$ as a string.

Applying the pumping lemma, we find that the part with $0^p$ needs to be pumped. So, even if it is pumped by one 0 at a time, we will soon get $0^{p+2}0^{p+1}$, which violates the constraints between $m$ and $n$.

# Answer
> 4 votes
Some people can be absolutely sure, and at the same time absolutely wrong. In this case, you are one of those people.

A language is a set of strings. A language is *not* the rules that were used to express the language. $0^\*$ and $\\{0^m 0^n: 0 ≤ m ≤ n\\}$ are the same language, even when that language is expressed in two different ways. And $0^\*$ and $\\{0^m 0^n: m ≥ n ≥ 0\\}$ is again the exact same language, just expressed differently.

Your attempted "pumping lemma" proof fails for the same reason: For example, $0^5 0^4$ is in the language, because it is exactly the same string as $000000000$, which is again the exact same string as $0^0 0^9$.

# Answer
> 3 votes
Your language is the same as $0^\*$ (and so, regular), since you can always choose $m = 0$. More formally, clearly your language is a subset of $0^\*$. Conversely, for any $n$, your language contains $0^n$ since $0^n = 0^0 0^n$ and $0 \leq 0 \leq n$.

More generally, when we are not sure about something in mathematics, we try to prove it. You claim that the language is not regular, but you don't have any argument. Your friends claim that their language is regular, and they do have an argument. If their argument is valid, then the only conclusion is that the language *is* regular.

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


# Question
Title: Why there is a probability in the completeness part?
**Interactive Proof System** : An interactive proof system for a language $L$ is a two-party game between a verifier and a prover that interact on a common input in a way satisfying the following properties:

1. The verifier strategy is a probabilistic polynomial-time procedure (where time is measured in terms of the length of the common input)
2. Correctness requirements:
3. **Completeness:** There exists a prover strategy $P$, such that for every $x ∈ L$, when interacting on the common input $x$, the prover $P$ convinces the verifier with probability at least $\frac{2}{3}$.
4. Soundness: For a false assertion, no convincing proof strategy exists (in the case of NP, if $x \notin L$ then no witness $y$ exists).

**My Question :** In the completeness part why there is a probability comming into picture?

# Answer
> 4 votes
The standard definition of $\mathsf{IP}$ involves probability both in the completeness and soundness requirements. Removing randomness all together reduces $\mathsf{IP}$ to $\mathsf{NP}$ (the witness is the full accepting transcript).

Note that you can amplify the success probability by "repeating the protocol" (i.e. talking with a prover $P'$ who simulates repetitions) and taking the majority vote (you need to be slightly careful here, since your dealing with a special prover who has access to previous interactions, but you're saved by the universal quantifier in the soundness requirement).

If what's bothering you is the fact that the protocols you are familiar with satisfy completeness with probability $1$, then one example is the proof for graph non isomorphism being in $\mathsf{AM\[2\]}$, using the set lower bound protocol, where the completeness probability is smaller than 1.

That said, you can in fact remove the probability from the completeness requirement (i.e. say that there exists a prover which convinces $V$ with probability $1$, $V$ is still probabilistic) without changing the class $\mathsf{IP}$, but this is a non trivial fact, which follows from the protocol for TQBP in the $\mathsf{IP=PSPACE}$ proof (which succeeds with probability 1 in case the formula is true).

---
Tags: complexity-theory
---


# Question
Title: "Any problem whose domain is finite is always Decidable", is true or false?
Question no:$1$

> "Any problem whose domain is finite is always Decidable"

lets take a TM,$M$ and finite domain of problem i.e. finite set of strings for eg. {$a,abaa,bba$}, Now the problem "whether $M$ accepts these set of strings or not is decidable or not?"

What I think is, this is Undecidable problem because, if $M$ loops forever any of these string then we not determine whether turing machine accept it or not.so according to this logic above statement is false.

Question no:$2$

Does a single instance of "turing machine's halting problem" is decidable?
As I given above example, I think this is also Undecidable.

# Answer
> 2 votes
It's not so clear what is "a problem whose domain is finite". Let me assume that what is meant by this is *a finite language*. Every finite language is decidable. The Turing machine compares the input to each word in the language, accepts if it finds a match, and rejects otherwise.

This answers your first question. Your second question is a special case of the first one.

---
Tags: turing-machines, undecidability
---


title: Number of DFA states required

text:
# Question
Title: Number of DFA states required
What is the minimal number of DFA states required to recognize binary numbers (encoded MSB to LSB) which are divisible by 6 and 8?

For divisibility by $6$ we required $6$ states.

For divisibility by $8$ we require $4$ states.

So in total, we need $6 \times 4$ states = $24$ states.

Am I correct? Can we do it with fewer states?

# Answer
> 1 votes
In order to obtain an *upper bound* on the number of DFA states required to recognize some language, the simplest method is to give a DFA with that (or lower) number of states. In order to obtain a *lower bound* on the same number, the easiest route is to give $m$ pairwise indistinguishable words. These are $m$ words $x\_1,\ldots,x\_m$ such that for each $i \neq j$ there exists a word $y$ such that $x\_i y \in L$ whereas $x\_j y \notin L$, or vice versa. This set of words shows that every DFA for $L$ must contain at least $m$ states (why?).

In your case, the minimal number of states is much smaller than 24, though the exact number depends on the encoding. Instead of solving your question, let me calculate the minimal number of states in a DFA accepting all (non-empty) decimal numbers (encoded MSB to LSB) which are divisible by 6. I claim that this number is 4. For the upper bound, consider a DFA with states $q\_0,q\_1,q\_2,q\_A$, where $q\_0$ is the initial state and $q\_A$ is the accepting states. The transition table of the DFA is $$ \begin{array}{c|ccccccccccc} \delta & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\hline q\_0 & q\_A & q\_1 & q\_2 & q\_0 & q\_1 & q\_2 & q\_A & q\_1 & q\_2 & q\_0 \\ q\_1 & q\_1 & q\_2 & q\_A & q\_1 & q\_2 & q\_0 & q\_1 & q\_2 & q\_A & q\_1 \\ q\_2 & q\_2 & q\_0 & q\_1 & q\_2 & q\_A & q\_1 & q\_2 & q\_0 & q\_1 & q\_2 \\ q\_A & q\_A & q\_1 & q\_2 & q\_0 & q\_1 & q\_2 & q\_A & q\_1 & q\_2 & q\_0 \\ \end{array} $$

You can show by induction that upon reading a word $w$:

* If $w = \epsilon$ or $w \equiv 3 \pmod{6}$, the machine is in state $q\_0$.
* If $w \neq \epsilon$ and $w \equiv 1,4 \pmod{6}$, the machine is in state $q\_1$.
* If $w \neq \epsilon$ and $w \equiv 2,5 \pmod{6}$, the machine is in state $q\_2$.
* If $w \neq \epsilon$ and $w \equiv 0 \pmod{6}$, the machine is in state $q\_A$.

This easily implies that this DFA accepts our language.

For the lower bounds, we use the set of words $\\{0,1,2,3\\}$. The following table gives the words $y$ separating each pair of words: $$ \begin{array}{c|cccc} y & 0 & 1 & 2 & 3 \\\hline 0 & & \epsilon & \epsilon & \epsilon \\ 1 & \epsilon & & 2 & 0 \\ 2 & \epsilon & 2 & & 0 \\ 3 & \epsilon & 0 & 0 & \end{array} $$ (These correspond to the states $q\_A,q\_1,q\_2,q\_0$.)

---
Tags: finite-automata
---


# Question
Title: Finding non-trivial NFA that accepts all short strings
It is well-known that every non-trivial NFA of $k$ states (an NFA that does not accept all strings) rejects a string of length at most $2^k$.

But is this upper bound asymptotically tight ?

I found a rough sub-exponential bound in this strategy.

Let $p\_i$ be an $i$-th prime.

On the singleton alphabet, $\Sigma = \\{a\\}$, the following NFA rejects only

$\\{a^n:n\>0, p\_1\cdots p\_k|n\\}$. With $p\_1+p\_2+\cdots+p\_k+O(1) = \Theta(k^2\log k)$ states.

Initial state $q$, is an acceptance state and it is branched into $k$ cycles with $\epsilon$ marks.

Every $i$-th cycle has $p\_i$ states, and only rejecting state is the state directly linked into initial state $q$. All of its transition are marked by $a$.

It is clear that the complement of accepting language is $\\{a^n:n\>0, p\_1\cdots p\_k|n\\}$ as given.

But $p\_1\cdots p\_k=O(e^{\Theta(k\log k)})$. which is sub-exponential with respect to $\Theta(k^2\log k)$.

In this unary and multiplication strategy it seems to be this is optimal because $\text{lcm}\\{p\_1,p\_2,\cdots,p\_n\\}$ is probably maximized with constraint $p\_1+\cdots+p\_n=C$ under this prime summation partition.

It seems we should use multi-ary language to improve this bound. Is there any suggestion or results in research?

# Answer
> 2 votes
Your question is very similar to a similar question about regular expressions. My answer there (citing a paper of Jeff Shallit and his students) gives an example in which the minimal word not accepted has length exponential in the number of states (using the fact that a regular expression of length $\ell$ can be converted an NFA of length $O(\ell)$). Moreover, the NFAs are over a *fixed* alphabet.

---
Tags: finite-automata, nondeterminism
---


# Question
Title: How does the number of clauses affect the difficulty of a 3-SAT problem?
What is the relationship between the number of clauses and the difficulty of a 3-SAT problem?

# Answer
In general, there is no connection. An instance with a "small" number (say a few thousands) of clauses can be very difficult to solve in practice, while an instance with a "large" number (say several millions) of clauses is easy. It's the structure that matters, not the number of clauses.

For *random* 3-SAT, you can have a look at the satisfiability threshold.
> 4 votes

# Answer
So, this all depends on what you mean by relationship.

In terms of traditional time complexity, all known algorithms solving 3SAT are, at best, exponential. To be precise, this means that if $f(n)$ is the function mapping an input size $n$ to the *maximum* time the algorithm takes on any input of size $n$, then $f$ is in $\Theta(b^n)$ for some $b \geq 1$.

However, in practice, adding clauses can speed things up, particularly if they are the *right* clauses. This is how, for example, Conflict Driven Clause Learning works. When backtracking search fails, CDCL "learns" a new clause which must be true (or else the search wouldn't have failed). It can then restart its search. The additional clauses add constraints that, when unit propagation is performed (i.e. when $p$ holds, we remove all $\lnot p$ occurrences from clauses), can prune out large portions of the search space.
> 1 votes

# Answer
3-SAT is a decision problem, like all NP-complete problems (because that's the way NP is defined). So you look at an instance of the problem, and have to decide whether the answer is YES or NO.

For most NP-complete problems, you can find sequences of instances that start with an instance where it is very easy to prove that the answer is YES, and as you look at other instances this becomes harder and harder to proof, then the correct answer changes to a very hard to prove NO, and further instances make it easier and easier to prove that the answer is NO.

That's what happens if you add more and more clauses to a 3-SAT instance. As you add clauses, it gets harder and harder to satisfy them all. And then you add one more clause that makes it impossible to satisfy all the clauses, which will be very hard to prove. As you add more and more clauses, that proof gets easier.
> 0 votes

---
Tags: complexity-theory, satisfiability, 3-sat
---


# Question
Title: Which type of control unit used in modern processor?
Is it hard wired CU or microprogramed?

# Answer
x86 are famous for using microcode, because there are a few complex operations, such as call gates or how the x87 calculates sines or exponentials, which cannot be reasonably constructed with a simple finite state machine. x86 also have very extensive patching resources, which allows to fix some bugs on released silicon, and which is probably handled through microcode (Some hints are probably in the patents from Intel and AMD).

Small ARM CPUs don't need and don't use microcode. The "R" and "M" classes.

High end ARMs such as Apple's... Who knows ? Besides the visible instruction set, there are also many hidden stuff, for example for debugging, self-testing the hardware and for power management, which may be based on microprograms.

The general trend nowadays, is that, even in x86, the instructions that need performance are decoded directly which is faster and more power efficient that fetching microcode memory.
> 3 votes

# Answer
Have a look at this article from 2010: https://www.realworldtech.com/sandy-bridge/ describing a popular real-world processor.

Even in 2010, "hardwired control unit vs. microprogrammed" doesn't make sense anymore. The model where the processor reads an instruction, then executes it, isn't how processors are implemented anymore.
> 3 votes

---
Tags: computer-architecture
---


# Question
Title: What are the examples of trivial and non-trivial properties of language recognized by a Turing machine?
**Rice's theorem:** Any nontrivial property about the language recognized by a Turing machine is undecidable.

I know the proof but I am not able to understand the theorem. I think trivial properties are like :language recognised by Turing machine contain at substring "aab". where as nontrivial property means is language accepted by Turing machine is finite etc.

**My question :** Give at least two example of trivial properties and two non-trivial property about the language recognized by a Turing machine.

# Answer
In the context of Rice's theorem, a trivial property has a very specific meaning.

Here, we define a property to be a set of Turing-recognizable languages. A property is non-trivial unless it contains no languages, or contains all Turing-recognizable languages.

We can clearly recognize these with a Turing Machine, since we can just make a machine that always says "YES" for the first case, or make a machine that always says "NO" for the second.

So both the properties you have identified are non-trivial properties, and are thus undecidable by Rice's theorem.
> 1 votes

---
Tags: turing-machines
---


title: Geometric intuition behind VC-dimension

text:
# Question
Title: Geometric intuition behind VC-dimension
Recently, I learnt about VC-dimension and how its boundedness assures PAC learnability on uncountable range spaces (let's assume that hypothesis class is the same as the family of concepts we want to learn).

My question is simple: What is/are the geometric intuition(s) behind the concept of VC dimension?

# Answer
> 2 votes
The VC dimension is a complexity measure for a family of boolean functions over some domain $\mathcal{X}$. Families who allow "richer" behavior have a higher VC dimension. Since $\mathcal{X}$ can be arbitrary, there isn't a general geometric interpretation.

However, if you think of $\mathcal{X}$ as $\mathbb{R}^d$, then you can think of binary functions as manifolds, whose boundary is what's separating positive and negative labels. Families with more "complex" boundaries have a high VC dimension, whereas simple manifolds do not, e.g. the dimension of linear separators is $O(d)$, while convex polygons (with unbounded number of edges) have infinite VC dimension. The more complex you allow the boundary to be, the more likely it is that you can find a large set for which you can agree with any labeling, by avoiding the negative labels in a "snake like" shape.

---
Tags: learning-theory, vc-dimension
---


# Question
Title: Is it possible to simulate a CPU with software?
I know it sounds a bit silly, but I got really curious. Is it possible to simulate a CPU in, let's say, Python? Some have argued that Minecraft, for instance, allows one to build turing-complete machines, but has some real research been made on this idea? Nested computers? How efficient could that be if made on assembly level? What about a **computer matrix**?

# Answer
Yes, its possible to simulate a CPU with software. A CPU is just an electronic implementation of a large, but finite, number of rules of the form "If this condition is true, modify the state like this" and software can certainly do that. Wouldn't it be surprising if it couldn't? CPUs are designed to support the sorts of things we want to do with software, so it would be very strange if they were radically different.

Indeed any system that has a finite state (i.e., can be described with a finite amount of data) and is manipulated by a finite set of rules can be simulated in software. Going further, I don't think there is any known physical process that can't, at least in principle, be simulated in software.
> 1 votes

---
Tags: algorithms, turing-machines, cpu
---


title: Nontrivial examples of sparse languages

text:
# Question
Title: Nontrivial examples of sparse languages
A language $L$ is said to be sparse if there exist a polynomial $p$ such that $|L \cap \\{0,1\\}^n| \le p(n)$.

One trivial example is suppose language is over single alphabet $1$ then $$L = \\{1^n | n \in Z^+\\}$$

**Question :** What are the other non-trivial examples of sparse languages?

# Answer
I don't think that there exists a reasonable characterization of all sparse languages (for instance, it's trivial to define sparse languages that sit arbitrarily high on the arithmetical hierarchy).

However, since $\\{0,1\\}^\*$ has exponential growth, you need to be able to derive some kind of combinatorial property from the language definition. For example, let $k$ be a constant and consider the following language:

$\qquad L = \\{x \mid x \text{ contains $k$ ones}\\}$

$L$ is sparse, the key observation being that $\binom{n}{k}$ for a fixed $k$ is a polynomial in $n$.
> 5 votes

---
Tags: complexity-theory, computability
---


# Question
Title: Regularity of a language with odd and even positions containing an even number of 1's
Given an alphabet $\Sigma = \\{0, 1\\}$ and a formal language $$L = \\{ w \in \Sigma^\* |\ |\mathrm{odd}(w)|\_1, |\mathrm{even}(w)|\_1 \text{are even numbers} \\}$$

That means that the number of 1's in the odd and even positions of a given string are always an even number. I've tried using the Pumping-Lemma on a $1^{4n}$ string but to no avail.

Any ideas how I can proove it is not regular. (I strongly assume it isn't regular).

# Answer
> 1 votes
To create the DFA, just start doing it. I assume there is no requirement that the number of elements in the string is even.

You start in the state A. In state A, you have an even number of 1's in the even and odd positions (initially, both counts are 0), so A is an accepting state. To get to an accepting state again, there must be a string following with an even number of 1's in the even and odd positions.

In state A, the next symbol can be 0 or 1. In case of 0, you have the exact same situation again, you need another string following with an even number of 1's in the even and odd positions. So A followed by 0 goes to A.

If the next symbol is 1, then the rest of the string must have an even number of 1's in even positions, and an odd number of 1's in odd positions. That's another state B.

In state B, if the next symbol is 0 then you now need an even number of 1's in odd positions, and an odd number of 1's in even positions. That's a new state C. In state B, if the next symbol is 1 then you now need an odd number of 1's in even and odd positions. That's a new state D.

Now you do the same for states C and D, and you find that whatever the input, you'll end up in one of the states A, B, C and D.

Don't think about "state" as some abstract state in a DFA. Think of it as something that you can describe in words. From any state, which you can describe in words, you get to another state, which you can describe in words again. If you compare those descriptions, and they are the same, then the state is the same.

The case where you don't get a DFA is when the number of states is not finite. For example, for $0^n1^n$, the initial state is "I need any number n of 0's and the same number n of 1's". If you get a 0 then you get a state where you need any number n of 0's and n+1 1's. Another 0 and you need n 0's and n+2 1's. And so on. The number of states is not finite. In your problem, there are only four states needed.

If that's too practical, then given any prefix X of a string in the language L, define the set of suffixes Y such that XY is in the language. Any such set of suffices is a state. An accepting state is one where the set contains the empty string. The initial state is the set of suffices when X is the empty string. In your case, there are only four different sets of suffices.

# Answer
> 0 votes
The following general result holds:

> Let $L = \\{ w : \mathrm{odd}(w) \in L\_1 \text{ and } \mathrm{even}(w) \in L\_2 \\}$. Then $L$ is regular iff $L\_1,L\_2$ are regular.

Indeed, suppose first that $L$ is a regular language over the alphabet $\Sigma$. Define a substitution $s\colon \Sigma \to 2^{\Delta^\*}$, where $\Delta = \\{ \sigma, \sigma' : \sigma \in \Sigma \\}$ by $s(\sigma) = \\{\sigma, \sigma'\\}$ and the homomorphism $d\colon \Delta \to \Sigma^\*$ by $d(\sigma) = \sigma$, $d(\sigma') = \epsilon$. Using $\Sigma' = \\{ \sigma' : \sigma \in \Sigma \\}$, we have $$ \begin{align\*} L\_1 &= d(s(L) \cap (\Sigma\Sigma')^\*(\Sigma+\epsilon)), \\ L\_2 &= d(s(L) \cap (\Sigma'\Sigma)^\*(\Sigma'+\epsilon)). \end{align\*} $$ This shows that if $L$ is regular then $L\_1,L\_2$ are regular.

In the other direction, suppose that $L\_1,L\_2$ are regular. Let $s\_1\colon \Sigma \to \Sigma^\*$ be the substitution $s\_1(\sigma) = \\{ \sigma \tau : \tau \in \Sigma$, and let $s\_2\colon \Sigma \to \Sigma^\*$ be the substitution $s\_2(\sigma) = \\{ \tau \sigma : \tau \in \Sigma \\}$. Then $$ L = (s\_1(L\_1) \cap s\_2(L\_2)) \cup d(s(s\_1(L\_1)) \cap s\_2(L\_2) \Sigma \Sigma'), $$ showing that $L$ is regular if $L\_1,L\_2$ are regular.

---

Given DFAs for $L\_1,L\_2$, you can construct a DFA for $L$ as follows (the same construction works for NFAs):

* The set of states is $Q = Q\_1 \times Q\_2 \times \\{odd,even\\}$.
* The initial state is $q\_0 = (q\_{0,1},q\_{0,2},even)$.
* The final states are $F = F\_1 \times F\_2 \times \\{odd,even\\}$.
* The transition function is given by $\delta((q\_1,q\_2,even),\sigma) = (\delta\_1(q\_1,\sigma),q\_2,odd)$ and $\delta((q\_1,q\_2,odd),\sigma) = (q\_1,\delta\_2(q\_2,\sigma),even)$.

You can check that for a word $w$ of odd/even length, $$\delta(q\_0,w) = (\delta\_1(q\_{0,1},\mathrm{odd}(w)),\delta\_2(q\_{0,2},\mathrm{even}(w)),odd/even),$$ and so $\delta(q\_0,w) \in F$ iff $\delta\_1(q\_{0,1},\mathrm{odd}(w)) \in F\_1$ and $\delta\_2(q\_{0,2},\mathrm{even}(w)) \in F\_2$.

This also shows that if $L\_1,L\_2$ can be accepted by DFAs with $n\_1,n\_2$ states, then $L$ can be accepted by a DFA with $2n\_1n\_2$ states.

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


# Question
Title: Is the language in the description context free?
I am stuck on a question. Lets say there is a string that can be created from three alphabets a,b,c the condition is number of a\<= number of b\<= number of c. I can solve if there are a and b (two alphabets) but I am not able to solve for 3. Any help will be appreciated. Thanks

# Answer
The basic problem here is that context-free languages are not closed under intersection.

The example you give illustrates this. Thus, $\\{ w\in\\{a,b,c\\}^\* \mid |w|\_a \le |w|\_b\\}$ is context-free, and similarly, so is $\\{ w\in\\{a,b,c\\}^\* \mid |w|\_b \le |w|\_c\\}$. The intersection of these two languages $\\{ w\in\\{a,b,c\\}^\* \mid |w|\_a \le |w|\_b \le |w|\_c\\}$ is not context-free.
> 1 votes

---
Tags: formal-languages
---


title: Is $E_{LBA}$ turing-recognizable?

text:
# Question
Title: Is $E_{LBA}$ turing-recognizable?
I have seen a proof that $E\_{LBA}$ is not decidable. But is it at least turing recognizable? How to prove it?

*NOTE:* $E\_{LBA}$ is defined as the emptiness problem for Linear bounded automaton

# Answer
I just read the definitions, hence I am not an expert on LBAs, but I think that the non-emptiness problem $\overline{E\_{LBA}}$ is r.e., so the emptiness problem $E\_{LBA}$ can not be r.e., otherwise it would be decidable.

To see why $\overline{E\_{LBA}}$ is r.e., notice that to certify that an $LBA$ has nonempty language it suffices to exhibit a word $w$ and a trace $t$ proving that $w$ is accepted by the $LBA$. So, a semidecider only has to enumerate all such pairs $(w,t)$, and (effectively) check for each pair if it proves the $LBA$'s language nonempty.
> 1 votes

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


title: When to rebalance the AVL tree?

text:
# Question
Title: When to rebalance the AVL tree?
Consider we have an AVL tree.

Its left subtree A has disbalance coefficient has value +1 (meaning the right subtree has greater depth). Its right son has disbalance coefficient -1 (meaning left subtree has greater length).

If I understand correctly, we're looking for the most right vertex in the left subtree.

After deleting this specific vertex, what are possible cases regarding the tree rebalancing? When will it have to be rebalanced and when not?

Please correct me, if I've made any mistakes.

# Answer
Let $w$ be the node to be deleted

1) Perform standard BST delete for $w$.

2) Starting from $w$, travel up and find the first unbalanced node. Let $z$ be the first unbalanced node, $y$ be the larger height child of $z$, and $x$ be the larger height child of $y$. Note that the definitions of $x$ and $y$ are different from insertion here.

3) Re-balance the tree by performing appropriate rotations on the subtree rooted with $z$. There can be 4 possible cases that needs to be handled as $x$, $y$ and $z$ can be arranged in 4 ways. Following are the possible 4 arrangements:

a) $y$ is left child of $z$ and $x$ is left child of $y$ (Left Left Case)

b) $y$ is left child of $z$ and $x$ is right child of $y$ (Left Right Case)

c) $y$ is right child of $z$ and $x$ is right child of $y$ (Right Right Case)

d) $y$ is right child of $z$ and $x$ is left child of $y$ (Right Left Case)

Like insertion, following are the operations to be performed in above mentioned 4 cases. Note that, unlike insertion, fixing the node $z$ won’t fix the complete AVL tree. After fixing $z$, we may have to fix ancestors of $z$ as well (See this video if you have trouble visualizing the above mentioned cases).

Courtesy of Geeksforgeeks.
> 1 votes

---
Tags: data-structures, binary-trees, binary-search-trees
---


# Question
Title: If a problem is "not semi-decidable" and "not decidable" can we say it is "undecidable"?
I was under impression that when a Language (or problem) is not semi-decidable and not decidable then we can say it's undecidable and I think it makes sense also based on diagram.

However, in my assignment the TA struck out "undecidable" and wrote "not semi-decidable". Why is "undecidable" wrong if it's both not semi-decidable and not decidable?

# Answer
> 1 votes
Undecidable isn't wrong: "undecidable" means exactly the same thing as "not decidable". However, your TA is saying that you can make the strictly stronger statement that the set is not even semi-decidable. This implies that it's undecidable, but isn't implied by "it is undecidable".

Suppose you were, instead in a biology class. You wrote "This is not a lizard" and your TA crossed it out and wrote "This is not any kind of reptile." You're both right, but your TA's version has more information in it.

---
Tags: undecidability, semi-decidability
---


# Question
Title: Will the machine ever reach on any other state other than start state?
Given a TM M, will it ever reach any other state other than start state if it starts with blank tape ? Is the above problem decidable ?

I think that if a TM really reaches any other state other than start state then we can check the transitions and find out. But if it doesn't at any point of time then we can't say that it will never reach other state in future too so it results in infinite waiting.

So the problem is undecidable or R.E according to me but the answer is decidable.

Please tell me where am I going wrong .

# Answer
Say $M$ has start state $s$ and transition function $\delta$. Construct a new Turing machine $M'$ with $Q = \\{s, HALT\\}$ (where s != HALT) and $\delta'$ as it's transistion function, defined by the following. $s$ is again the start state and $HALT$ is the accept state.

$$ \delta'(s, x) = \begin{cases} s & \delta(s, x) = s \\ HALT & \mbox{otherwise} \\ \end{cases} $$

$M'$ will halt IFF $M$ ever transitions out of the start state.

If you know what the maximum shifts function is for two states and your symbols then you can simulate $M'$ for that many steps to determine if $M'$ halts or not. Non constructively even if we can't compute the busy beaver function for your number of symbols it has *some* value and therefore our argument still goes through.

This shows that, at least classically speaking, this problem is decidable. It also constructively shows that it's decidable for any number of symbols that we can constructively prove an upper bound on the maximum step function for. This algorithm runs in constant time...where the constant might be *very* large. So asymptotically it's ideal. I'm not sure if there's an algorithm that does this with a smaller constant but I'm betting it's not possible.
> 3 votes

---
Tags: computability
---


title: Reduction from P to NP

text:
# Question
Title: Reduction from P to NP
Conceptually, I know that reducing a problem $Y$ that's NP-complete to a problem $X$ implies that $X$ is at least as hard as $Y$, implying $X$ is also NP-complete. So if any NPC problem, say $Z$, can be solved in polynomial time, then that implies $P = NP$, since any other NP-complete problem can be reduced to $Z$ in polynomial time, and then solved in polynomial time. But what does it mean to reduce a problem in $P$ to a problem in $NP$? I feel like this is self-evident (problems in P are no harder than problems in $NP$), but is there any example that can make this clearer?

# Answer
Note: this answer assumes that we are considering polynomial-time reductions (and not e.g. log-space ones).

---

If $A$ belongs to $P$, then we can reduce $A$ to any nontrivial language, i.e. any $B\neq \emptyset,\Sigma^\*$.

Reducing $A$ to $B$ can be done as follows. Fix $b\_1\in B, b\_0 \in \overline B$ arbitrarily. The reduction algorithm then takes an input $x$ and tests whether $x\in A$: if that holds, return $b\_1$, otherwise return $b\_0$.

Note that all of this can be run in polynomial time since $A$ belongs to $P$. This allows to solve the $A$ instance in the reduction algorithm itself, trivializing the reduction.

This proves that problems in $P$ are indeed the easiest possible ones, according to the "polynomial-time reduction" preorder.
> 6 votes

---
Tags: complexity-theory, reductions, np
---


# Question
Title: NP-completeness of triangle removal problem
Triangle removal problem states that, given an undirected graph G, can you pick a subset S of vertices such that removing S will remove all triangles from the old graph and |S| \<= k. I was trying to use reduce from vertex cover problem, but every construction I attempted has failed. Here's what I've done:

1) Add extra edges to the graph such that every pair of distinct vertices is connected by an edge (In other words, create a complete graph Kn)

2) Create a subgraph of G, but only composed of vertices with degree at least 2 from the original graph

I found a counter example for each construction, and I can't fully grasp the starting point. The goal is that I want to build some graph out of an old graph such that the every triangle should use at least one vertex in S(solution returned by black box for "triangle removal problem"), but it has to be a vertex cover for the old graph at the same time. How should I approach this?

Edit: Current attempt - for every existing edge (u,v) in E in a graph, add a new vertex w and add two new edges (u,w) and (w,v) so that it forms a triangle

# Answer
Your current attempt (at the time of writing this answer at least) is on the right track, it just needs one more step.

To help understand one way of relating the problems to each other, consider the following alternative way of defining a vertex cover; a vertex cover is a set of vertices whose removal leaves a disconnected graph.

So Vertex Cover is the problem of selecting vertices to remove that gets rid of all edges, whereas your problem is selecting vertices to get rid of triangles.

Thus to convert Vertex Cover to Triangle Removal we need to turn edges in the original graph intro triangles in the new graph (or at least, one sensible way - there could be many reductions).

Hence your construction of adding a vertex for every edge in the graph and making a triangle is heading in the right direction, the only problem is that we could remove the new vertices, and that may mess up our answer (it certainly makes it harder to argue about what the vertex cover should be in the original graph). What we need is a way of preventing the added vertices being selected for removal. To do this, instead of adding a single new vertex, add $k+1$ new vertices!

More precisely (but not completely precisely), given $G$ we construct $G'$ as follows:

* For every vertex $v \in V(G)$, there is a vertex $v' \in V(G')$
* For every edge $uv \in E(G)$, there is an edge $u'v' \in E(G')$.
* For every edge $uv \in E(G)$, there are $k+1$ vertices $\\{w\_{1},\ldots,w\_{k+1}\\} \subseteq V(G')$ with the edges $u'w\_{i}$ and $v'w\_{i}$ in $E(G')$ for all $i$.

I won't go through the full proof that this works, but the general gist is that if we want to get rid of all the triangles attached to $u'v'$, it doesn't really help to take any of the $w\_{i}$ vertices as there are too many of them, we eventually have to take at least one of $u'$ or $v'$, but once we take one of those, it deals with all the triangles, so any answer that takes a $w\_{i}$ vertex must also take $u'$ or $v'$ (or both) and can be replaced by a smaller solution that takes only $u'$ or $v'$ (or both), so we only have to consider solutions of that form, but then we're basically done - as each edge has triangles, one of the two "original" vertices must be in the triangle removing solution for each edge, and hence is also a vertex cover.

Really you can make the same argument with your construction, but the additional vertices force things and make the argument clearer (you don't have to deal with arguing for alternative solutions and vertex swapping etc. etc.)
> 2 votes

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


# Question
Title: Data link layer Sliding Window utilization formula query
In the data link layer, the Sliding Window is used for flow control.

There are two link utilization formula that can be use. They are :

U = 1, for N \> 2a + 1

OR

U = N/(1+2a), for N \< 2a + 1

In both formula, N denotes the window size and a = Propagation time / transmission time

I am not really understanding which formula to use in what situation although the condition is specified. What does 2a+1 actually mean? Can anyone help me to understand it in simple term. Thanks!

# Answer
> 1 votes
If it is about how we got to the formula, link utilization is the ratio of the time that the link is active to the total time.

> total time being the sum of transmission time and propagation time.
>
> link active time = time taken to transmit N packets = N * TransmissionDelay

Hence, the formula to calculate link utilization(or efficiency) is

> N/(1+2a)

However, in practice, the link utilization cannot exceed 1 (ie link cannot be active for more than 100% of the time). Hence, whenever N\>(1+2a), we restrict the value to 1 only.

---
Tags: computer-networks, communication-protocols
---


title: How can I fit a sine function to a SVR?

text:
# Question
Title: How can I fit a sine function to a SVR?
I have a time series which represent the sine curve. Now I want a regressor to learn this curve, and being able to predict for future values.

PS: Sine curve is only for testing purposes. What I want is to learn that function and its parameters as well which need not be sine.

# Answer
> 1 votes
Use nonlinear regression: https://en.wikipedia.org/wiki/Nonlinear\_regression. Write down a model, e.g., $f(x) = \sin(\alpha x + \beta)$, and then try to find parameters $\alpha,\beta$ that minimize the regression error (the sum of the squared error at each point; i.e., square of difference between model's prediction and observed value). You can use gradient descent or other forms of mathematical optimization for that. If a sin function isn't the right model, you can write down some other model (with some parameters) and use optimization to find the best values for the parameters.

# Answer
> 1 votes
You could try symbolic regression (SR).

The general idea is finding a function that fits the given data points without making any assumptions about the structure of that function.

Genetic programming (GP) is well suited to this sort of task since it makes no such assumptions. SR was one of the earliest applications of GP and continues to be widely studied.

In general, SR is more computationally intensive and produces less accurate models than the other nonlinear technique.

---
Tags: machine-learning, time-series-analysis
---


# Question
Title: What is the time complexity of memory allocation assumed to be?
It is well-known that dynamic arrays have an amortized $O(1)$ time complexity for adding one item, but a worst-case $O(n)$ complexity. This is because for particular values of $n$, there is no more room in the buffer, so the dynamic array allocates a new buffer and copies over $n$ items.

My question is, what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$ time?

# Answer
> what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$ time?

This depends on what you mean by "allocate a buffer with size $O(n)$" and how much time that takes. Unfortunately, there isn't a standard answer for that. It boils down to how you *model* "allocating a buffer", and your *assumption* about the time complexity of that operation.

You could assume that allocating such a buffer could be done in $O(1)$, or you could assume that this takes $\Theta(n)$ time. It depends on the system you're trying to model:

* The operating system will generally overwrite memory that has previously been used by another process with all zeros to avoid leaking information from one process to another. Thus, allocating a size-$n$ buffer will take at least $\Omega(n)$ time due to this initialization procedure.
* If you are working in a very low-level setting (for instance assembly programming), "allocating a buffer" might you mean grabbing a pointer to the top of the heap and then incrementing that pointer by the number of elements you want to allocate. You could reasonably model this as an $O(1)$ operation.
* If you are, for instance, working in C and initialize a buffer by calling `malloc`, then there is generally no guarantee about the complexity of this operation. It might take $O(1)$ time, $O(n)$, $O(n^2)$, exponential time or even fail to allocate the buffer at all (out of memory). On the other hand, specialized implementations of malloc (such as TLSF) might come with guarantees.

Thus, depending on the *implementation*, the operation "allocating a buffer" should be *modeled* as having a different time complexity. If you are working in a purely theoretical setting (without any underlying implementation), then you have to make an assumption. Assuming it takes $O(n)$ time is more *reasonable* than assuming it would take $O(1)$ time (since more real-world systems will be able to meet the former assumption than the latter), however, any assumption, if clearly stated is valid. It is even possible to reason about totally unreasonable assumptions (for instance, you could assume that you could copy over $n$ items in $O(1)$ time) for the sake of argument.
> 6 votes

---
Tags: algorithm-analysis, data-structures, runtime-analysis, arrays, memory-allocation
---


title: Completeness problem of TM

text:
# Question
Title: Completeness problem of TM
$L = \\{ \langle M \rangle \mid L(M) = \Sigma^∗ \\}$

Is above problem R.E ?

I found an explanation in one of the websites and I have doubt in few lines of paragraph.

The explanation was

Now, given a halting problem $(\langle H \rangle, w)$, we proceed as follows: We make a new TM say $A$, which on input $x$, just simulates $H$ on $w$ for $|x|$ steps. If $H$ halts on $w$, $A$ goes to reject state. Otherwise it accepts. So, $L(A)=\Sigma^\*$ if $H$ does not halt on $w$ and $L(A) =$ a finite set if $H$ halts on $w$. So we can reduce non halting problem to this problem. Hence given language is non R.E

Can someone please explain me how is $L(A) = \Sigma^∗$ if $H$ does not halt on $w$ ? It says if $A$ doesn't halt within $|x|$ steps then $L(A)$ is infinite. How can we say that ? What it TM $A$ halts on $|x+1|$ th step? Even then it will be finite but this explanation considers it as infinite.

I understand how is it finite set if $H$ halts on w but I am not able to understand the non halting part.

# Answer
Assume $H$ does not halt on $w$. To prove $L(A) = \Sigma^∗$ we need to show that $A$ accepts every $x$. Indeed, whatever $x$ is, we simulate the execution of $H$ on $w$ for only $|x|$ steps (a finite, known amount of steps). I.e., we do not simply run that program on its own, we keep an "alarm clock" counting the steps $H$ as it is running, and as soon as it reaches $|x|$ the alarm rings and we stop the simulation. In this way, no matter what $H$ does on $w$, the simulation will always terminate: either because $H$ halts before $|x|$ steps, or because the alarm rings and we abort the simulation.

Now, since $H$ does not halt on $w$ by hypothesis, $H$ will always make the alarm ring. In such case, $A$ accepts $x$ by construction, hence $A$ indeed accepts all inputs $x$.

For the other direction, assume that instead $H$ does halt on $w$. Let's write $k$ for the number of steps that make $H$ halt on $w$. We now need to prove that $L(A) \neq \Sigma^∗$. Take $x = 1^k$: we prove that $A$ rejects it. By definition, $A$ simulates $H$ on $w$ for $|x|=k$ steps, and that's just enough time to make $H$ halt. So, by construction $A$ rejects.
> 3 votes

---
Tags: computability, turing-machines, semi-decidability
---


# Question
Title: Different decompositions of the string in the pumping lemma proof
Let $s = a^pb^{2p}$, now which one of those decomposition is correct:

$x=a^k$, $y=a^l$, $z=a^{p-k-l}b^{2p}$, where $k+l \leq p$

$x=a^{p-k}$, $y=a^k$, $z=b^{2p}$, where $1\leq k \leq p$

$x=\epsilon$, $y=a$, $z=a^{p-1}b^{2p}$

or are they the same? I've read in multiple answers that we don't get to pick the decomposition, but I'm not sure how to understand this, because to me all of those decompositions are legitimate.

# Answer
> 1 votes
Here is the statement of the pumping lemma:

> If $L$ is a regular language then there exists an integer $p$ such that every word $w \in L$ of length at least $p$ has a decomposition $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) for all $i \geq 0$, $xy^iz \in L$.

Here is the contrapositive, which is how you usually apply the lemma:

> Suppose that $L$ is a language such that for every $p$ there exists a word $w \in L$ of length at least $p$ such that **for every decomposition** $w = xyz$ satisfying $|xy| \leq p$ and $y \neq \epsilon$, there exists $i \geq 0$ such that $xy^iz \notin L$. Then $L$ is not regular.

When you apply the lemma to show that a language is not regular, you have to consider all possible decompositions satisfying $|xy| \leq p$ and $y \neq \epsilon$. For each of them you need to find an $i$ such that $xy^iz \notin L$.

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


title: Are URI's a regular language?

text:
# Question
Title: Are URI's a regular language?
Do URI's, as defined in rfc3986, form a regular language?

How can I tell?

There's a BNF grammar provided, but I don't know how to check that it has a unique representation of every URI, or that it describes a regular language.

# Answer
Here are some checks you can perform for yourself:

* Is there any recursion in the rules?
*No:* The language is finite, hence regular.
* Can the recursions all be written in the form of $A \to \alpha B$, with $\alpha$ a terminal string and $A$, $B$ non-terminals?
*Yes:* The grammar is (or can be transformed into an equivalent) right-regular (one), hence the language is regular.

If there are constructs like $A \to \alpha B \beta$ or even $A \to \alpha A \beta B \gamma$, then you'll have to look more closely, and there's no easy way: deciding whether a context-free grammar generates a regular language is, in general, undecidable (cf. Greibach's theorem). See our reference questions for techniques for showing either direction.
> 2 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Expressing conditional in linear program
I have two variables $A$ and $B$, with $A$ being binary and $B$ is a real number where $B \ge 0$. My conditions are:

```
if B > 0
         A = 1
else
         A = 0

```

How to express this as a linear program? I have figured out one condition using the big-M method:

$MA \gt B$

which means that if $B\>0$, then $A$ must be 1 to satisfy this constraint. However if $B=0$, then $A$ can be either 1 or 0, and I need another constraint. How to enforce $A$ to be 0 when $B=0$?

# Answer
> 4 votes
If you know the maximum value of $B$ then you can easily express all comparisons as described here: https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/

In your case you need the following:

$0 \le -B + MA \le M-1$

assuming that $M$ is big enough.

---
Tags: linear-programming, integer-programming
---


# Question
Title: Undecidable predicate logic is decidable by people?
Logic in computer science (By Michael Huth,Mark Ryan, second edition, page 132) says

> Every φ can, in principle, be discovered to be valid or not, if you are prepared to work arbitrarily hard at it; but there is no uniform mechanical procedure for determining whether φ is valid which will work for all φ.

For me, it sounds contradictory because I take your ability to decide any formula as a uniform mechanical procedure. If you can do it, then you have a uniform mechanical procedure. What do I fail to understand?

Just to be clear what validity means here, the discussion happens in the context of *validity definition*:

> Given a logical formula φ in predicate logic, does ⊨ φ hold, yes or no?

# Answer
> 5 votes
Keep in mind that the book was written for undergraduate students, and there are aspects of logic that will demand a considerable level of sophistication, which is often omitted at this introductory level.

Importantly, the sentence

> Every φ can, in principle, be discovered to be valid or not, if you are prepared to work arbitrarily hard at it.

is **not**, and cannot be, a sentence about proofs realized within the context of a formal theory, but as performed by people (possibly with the help of machines) in real life. *Taken out of context*, the sentence is obviously false, from any pragmatic standpoint. Moreover, it philosophically oversimplifies and confuses the subject, in a way that is in fact questionable, even from a didactic point of view.

That said, I wouldn't take these issues too seriously. Apparently, the book has many good qualities, and it is really hard to convey this kind of subject to the intended audience in a way that is both rigorous and inviting.

# Answer
> 8 votes
The author is incorrect. A consequence of Godel's incompleteness is that any sufficiently complex logic has statements that are true, but have no proof of truth.

If every statement had a proof or disproof, then we could iterate through all strings, check if it was a proof or disproof, and eventually we'd find one, making logic decidable. We know that this isn't the case, since this could solve the halting problem.

In the context of your question, this means there are valid formulas with no proofs of validity.

Humans have an excellent set of heuristics for proving things. We are good at seeing patterns and incorporating past knowledge. But ultimately we can't find proofs that don't exist.

---
Tags: computability, logic, undecidability, first-order-logic, logical-validity
---