# Tagged Questions

Questions about methods and techniques for proving theorems.

141 views

### What is wrong with this reasoning that finding the genus of a degree 3 bipartite graph is NP-complete?

Finding genus of a biparite graph is $NP$-complete and finding genus of a degree $3$ graph is $NP$-complete and so finding genus of a degree $3$ bipartite graph is $NP$-complete. Though implication ...
9 views

### Proof with closure properties for regular languages [duplicate]

Hi how to prove using properties closure for regular languajes that: $L = \{w|w \in \{a,b\}^* \wedge |w|_b = 2|w|_a \}$ is not regular. Thanks
32 views

### Proving weak simulation

I want to prove something but I am not sure if it is the right way to do it. I have two LTS that define different semantics. A=($Q_a,Λ,\to)$, and B=$(Q_b,Λ\cup\{\beta\},\leadsto)$, where $\beta$ is ...
62 views

### How to come up the number of nodes on a given level in heaps?

CLRS asked it's readers to prove that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$ in any n-element heap as an exercise. The principle of Mathematical Induction can be used to prove ...
24 views

### How would one prove that the following scheme definition is an ordered stream of integers

How would one prove that the following scheme definition is an ordered stream of integers (define integers (cons-stream 1 (add-streams ones integers)))
45 views

### Modal logic axiom S4, transitive and reflexive frame, tableaux solver

I have a difficult problem to solve which as mentioned in the title is related to modal logic axiom S4. So, here is some background knowledge that can be useful: S4 axiom is a class of transitive ...
33 views

### simple iterate algorithm proof by induction

Suppose I have a function where it calculates which bit is larger called LargerBinary. Let's say I have an input 110111;101001, the output will be 110111 and if the input is 110110:110110, the output ...
69 views

### Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

$$L = \{ \langle M \rangle \mid \text{$$M$$ is a Turing Machine and $$|L(M)| = 1$$} \}$$ I have to prove that this is not R.E. and not co-R.E. I know how to approach these kind of problems. For ...
277 views

### Can I simplify log(n+1) before showing that it is in O(log n)?

Had a question about the following: $$\log (n+1) \in O(\log n)$$ Can the left side be simplified any further or do I need to just go ahead and find a c and n that hold?
22 views

### How do I prove a language is regular? [duplicate]

I've done a lot of research on this topic, but still don't feel very confident about it. Let's say the example is: For a language L over an Σ, define N(L)={w∈Σ∗: wk∈L for some k∈Σ∗}. Prove that, if L ...
120 views

### How can I check constraints on my state machine behaviour?

My background is fairly practical rather than theoretical, so this question may be a bit basic. I have a state machine with events, and events may optionally trigger action functions to be called as ...
39 views

### Big-O Justification Question

I am trying to justify the big-O order of a runtime complexity by finding a $c$ and $n_0$ that hold for it. Does the left side of the justification need to be one or higher, or can it be any value so ...
69 views

### How not to prove that P ≠ NP implies NP ≠ PSPACE

Let's define the two variants of the Travelling salesmen problem: $TSP_{opt}$ : Give me the shortest tour $TSP_{dec}$ : Is there a tour of $l$ or shorther (Yes/No) Now assume $P \neq NP$: Since ...
78 views

### Is the NP-hardness Proof with One Way Implication Correct and Why?

A problem $\Pi$ is NP-hard if I can prove this: a known NP-hard problem $\Pi'$ reduces to $\Pi$ in polynomial time; and $f(x) \in \Pi\iff$ $x \in \Pi'$. If I can show only one way implication, ...
20 views

### Can I change the input of my reductionduring the proof?

To prove that a problem $\Pi_2$ is NP-hard one has to: select a known NP-hard problem $\Pi_1$; from an arbitrary instance of $\Pi_1$, create an instance of $\Pi_2$ in polynomial-time; and show ...
80 views

### proof using induction of automaton

How I can explain this. Consider the following automaton, $A$. Prove using the method of induction that every word/string $w\in L(A)$ contains an odd number(length) of $1$'s. Show that there are ...
106 views

### Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates

A Boolean function $f : \{0, 1\}^n → \{0, 1\}$ is called monotone if changing any of the $n$ input bits $x_1, \ldots , x_n$ from $0$ to $1$ can only ever change the output $f(x_1, \ldots ,x_n)$ from ...
49 views

### Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: ( a + b )* a ( a + b )* b( a + b )* = (a + b)* ab(a + b)* I can ...
48 views

28 views

### Tools or techniques for studying the language a CFG produces? [duplicate]

When developing a CFG, I find that one can be confused about whether the grammar is correct, i.e. whether it recognizes only the required strings and not other strings. But this can be hard to see? ...
391 views

### Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

Every undecidable problem that I know of falls into one of the following categories: Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the ...
54 views

### How Splitting Summation method works

I'm reading Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and ...
100 views

77 views

### Do polynomial reduction functions work both ways?

For example to prove 3-Sat ≤p Independent Set do I just have to prove this theorem: Theorem- Formula F is satisfiable IFF graph has an independent set. If I have to prove it this way does this also ...
499 views

### How do I verify that a DFA is equivalent to a NFA?

I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is ...
243 views

### Why do puzzles like Masyu lie in NP?

The puzzle is made up of (n x n) squares so when taking the problem the input size would be n. Rules of Masyu: The goal is to draw a single continuous non-intersecting loop that properly passes ...
108 views

### Languages that are not subset, but are union

Are there examples of regular languages $L_1$ and $L_2$, where $L_1$ and $L_2$ is not a subset of each other but that $(L_1 \cup L_2)^* = L_1^* \cup L_2^*$ ?
51 views

### Why if $G$ has two spanning trees $A$ and $A'$, then every edge of $A'\cup \{e_i\}\in A'$

Theorem: Let be $G$ a weighted graph in which every edge has a different weight. Suppose that $G$ has two spanning trees $A$ and $A'$. Let be $i$ the first index such that $e_i\ne e'_i$ ...
19 views

### Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle?

I am studying the algorithm of Sollin and we recently studied a lemma: Let be G a graph which values are diffferent on the edges. We sort the edges $e_1,e_2,...e_m$ such as $v(e_i)<v(e_j)$ ...
47 views

### Understanding the proof of the halting problem [closed]

I came across the following example that proves that the blank tape halting problem is not decidable. I understand the proof technique, but I just don't see how the blank tape problem is shown to ...
22 views

### Method of inductive statements for proving partial correctness of block-schemes

I'm trying to find an explanation and more information on a method and some example problems with solutions using that method. The method doesn't seem to translate well in english (I'm from a ...
95 views

6k views

### Proof that dead code cannot be detected by compilers

I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the ...
81 views

### Solving recurrences by substitution method: why can I introduce new constants?

I am solving an exercise from the book of Cormen et al. (Introduction To Algorithms). The task is: Show that solution of $T(n) = T(\lceil n/2\rceil) + 1$ is $O(\lg n)$ So, by big-O definition I ...
44 views

### Optimal prefix code: full binary tree existence

I'm ok following the passages generally used to prove this theorem, like in this question concerning the same subject. Anyway i've the unpleasant feeling that the proof lacks something to be ...
170 views

### How rule 110 would be proven to be universal if the tag system did not exist?

I was reading about Cellular Automata and I read in this question that Matthew Cook proved that rule 110 is universal, and that his proof relied upon showing how rule 110 can simulate a tag system. ...
Let's define the following operations: $odd(string) =$ odd characters of $string$, $even(string) =$ even characters of $string$ Now say we have some language $L$, we will then define the ...
What would be the general approach for that? And what are the things that generally overlooked while proving such things? For example, I have a Language, L ={e:$L(M_e)$ such that it accepts only 'a ...