Questions about methods and techniques for proving theorems.

learn more… | top users | synonyms

6
votes
1answer
76 views

How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
0
votes
1answer
24 views

When reducing from HALT, can you create a Turing machine that asks whether a simulation stops?

Lets say I am doing a reduction from $\mathrm{HALT}_{\mathrm{TM}}$ to another language $S$, in order to prove that $S$ is not decidable. For this I need to build a new Turing machine, $M'$. Can I ...
3
votes
1answer
26 views

Question regarding Karp-Lipton theorem

In the proof in wikipedia, it goes like this: Let $L \in \Pi_{2}$, so we can describe membership in $L$ as a formula: $\forall_{y}\exists_{z} V(x,y,z)=1 \iff x \in L$ (where V is polynomial ...
3
votes
1answer
17 views

How to handle an undefined case with µ-recursive functions?

How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators? For ...
0
votes
2answers
71 views

How to prove that a language $A$ is decidable?

How to prove: A language $A$ is decidable $\Leftrightarrow$ if there is a turing machine which lists $A$ in a word length alphabetically ordering. Word length alphabetically means a sorting first ...
3
votes
3answers
302 views

Structure of a Pumping Lemma proof: contradiction or counterexample?

This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact ...
0
votes
0answers
25 views

Proof of RAP-derivation sequence for a set of functional dependencies in relational databases

I'm reading David Maier's outstanding but out-of-print book on relational databases (the book,"The Theory of Relational Databases", is available online from the author's website http://web.cecs.pdx....
0
votes
0answers
26 views

Structural induction hypothesis on derivations

I am relatively new to the field of language semantics, however i am a bit confused about using operational semantics and structural induction on Derivations. If I have two languages $L1$ and $L2$ and ...
1
vote
2answers
47 views

Prove the halting problem is undecidable using Rice's theorem

Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed: We want to reduce Rice's Theorem (decide if a language has the nontrivial ...
-1
votes
1answer
44 views

What do we mean when we say an edge (u,v) connects some component to other component in forest G = (V,A)

Let H = (V,E) be a connected, undirected graph. Let A be a subset of E. Let C = (W , F) be a connected component (tree) in the forest G = (V,A). Let (u,v) be an edge connecting C to some other ...
1
vote
3answers
145 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 ...
2
votes
0answers
38 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 ...
3
votes
1answer
66 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 ...
0
votes
0answers
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)))
1
vote
0answers
51 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 ...
0
votes
0answers
35 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 ...
1
vote
1answer
77 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 $\...
1
vote
3answers
280 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?
0
votes
0answers
23 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 ...
3
votes
1answer
121 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 ...
0
votes
2answers
41 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 ...
0
votes
0answers
73 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 $...
3
votes
1answer
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, ...
1
vote
1answer
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 ...
-1
votes
2answers
82 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 ...
1
vote
2answers
107 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 $...
0
votes
1answer
55 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 "see"...
3
votes
1answer
50 views

Why add a +1 to the constant proving an O(n) bound?

I have calculated a running-time function $T(n) = 4 + 4n$, which is $O(n)$. To determine the constant $C$ given by the relation $|T(n)| < C \cdot g(n)$, we take $\qquad\displaystyle \lim_{n \to ...
0
votes
2answers
69 views
0
votes
0answers
9 views

Proving the Multiway cut problem is NP Complete [duplicate]

Problem Statement: Given k nodes: $$ u_1, u_2, u_3..., u_k $$ remove edges of total minimum weight that separates $u_i$ from $u_j$ for all $i != j$ for all k >= 3 I just need some help identifying ...
3
votes
2answers
86 views

Determining states in a DFA

In computational theory for deterministic finite automata, there is a 5-tuple representation containing $Q$, $\Sigma$, $\Delta$, $Q_0$ and $F$. I am wondering how one understands thinking about the ...
0
votes
0answers
24 views

Is there a general form of polynomial reductions in complexity theory? [duplicate]

While reading Sipser, in computability I read about many to one mapping reducibility and Turing reducibility,the latter one being a more general form of reducibility. But in the introductory chapter ...
4
votes
2answers
727 views

Is a single string enough to prove regular expressions inequivalent?

Which of the following regular expressions generate a language that is different from the rest? (a+b)$^*$a(a+b)$^*$(a+b)$^*$ b$^*$ab$^*$a(a+b)$^*$ (a+b)$^*$ab$^*$ab$^*$ b$^*$ a(...
2
votes
1answer
62 views

Prove that every thin AVL tree may be converted to red-black tree

Let's define thin AVL tree as AVL tree $t'$ such that contains minimal possible number of nodes among all AVL tree $t$ such that $height(t)=height(t')$. I am trying to prove that every thin AVL ...
1
vote
2answers
110 views

Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$?

I've read a proof explaining why $A_{\mathrm{TM}}$ is undecidable, and I don't seem to understand why we need to give the opposite of $H$ function $D$ itself as input. Here's the copy-paste of that ...
3
votes
2answers
70 views

Choosing nonzero entries from an array so no pair in same row or column

Suppose we have an $n\times n$ array $A$ of non-negative real numbers in which the sum of each row and each column is $1$. We want to find $n$ entries of the array $(x_1,y_1), \dots, (...
-1
votes
1answer
29 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? ...
25
votes
2answers
414 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 ...
1
vote
1answer
55 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 ...
0
votes
3answers
111 views

Proving/Disproving that language L is non-regular/CFL

Here are three examples of questions I run into. I'm not looking for solutions. If $L$ is CFL then $L' = \{ ww^R | w \in L \}$ is non-regular. If $L$ is non-regular then $L' = \{ ww^R | w \in ...
-1
votes
2answers
135 views

How to simplify boolean expression? [closed]

I am having trouble simplifying logical expressions to a much simpler form, can someone provide me some insight on how to approach the problem? Let's assume i have the following expression: $ABCD + A\...
1
vote
1answer
82 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 ...
10
votes
3answers
535 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 ...
2
votes
1answer
246 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 ...
0
votes
1answer
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^*$ ?
0
votes
0answers
55 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$ ...
0
votes
2answers
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)$ ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
97 views

How do I prove that a language is deletion closed?

For example, how could I prove that the following language is deletion closed: {$a^k$$b^j$ : $j$, $k$ $\geqslant$ 0} The reason seems obvious to me, I just can't see a way to prove it.