Questions about methods and techniques for proving theorems.

learn more… | top users | synonyms

0
votes
0answers
12 views

How to formally prove: if d|(da+b), then d|b? [migrated]

How would I formally prove that for the integers a, b, and d If d|(da+b), then d|b. Would a direct proof be the best option? If I do a direct proof I seem to get stuck pretty quickly... in fact I ...
3
votes
1answer
100 views

Prove that regular expression is unambiguous

I've got following definition: Function $f$ is a valid mapping of word $w$ to regular expression $R$, if any of following conditions is true: $R = w$ and $f$ is the identity or $R = \epsilon$ and ...
0
votes
1answer
24 views

Hoare logic - partial/total correctnes and strength invariant

I'm studying Hoare logic and I can't understand the relation between partial and total correctness regarding loop invariant. Suppose for example that I have the following program: ...
10
votes
3answers
675 views

Is it really possible to prove lower bounds?

Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use ...
4
votes
1answer
60 views

Techniques to prove a language is not DCFL

I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL. Are there any other techniques that will help me to ...
0
votes
1answer
40 views

How do you prove two languages are equivalent using the definition of acceptance?

I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$ where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ ...
2
votes
1answer
41 views

Proof via induction for small-step semantics

I'm doing a course in Computer Programming Languages and I'm trying to prove the following (roughly following Pierce's Types and Programming Languages book): if $t \rightarrow^* t'$ then $if\; t\; ...
3
votes
2answers
41 views

How to pick a good structural induction hypothesis

(Full disclosure: homework question) Let $M = (Q, \Sigma, q_0, A, \delta)$ be a finite automaton. The extended transition function $\delta^*$ is defined as follows: $\forall q \in Q$ $\delta^*(q, ...
2
votes
0answers
34 views

What are the fundamental principles/algorithms on the process of equation solving?

I have seen a lot of solvers that are capable of, for example, getting an equation such as x ^ 2 + x = 12 and finding x = [3, -4]. I know some of them are implemented by hardcoding special cases. For ...
3
votes
1answer
40 views

Birkhoff-von Neumann theorem for bistochastic digraphs

A weighted digraph (with loops) is bistochastic, iff the weights are non-negative, for all non-sink nodes, the sum of the edge weights of the out-edges is $1$, and for all non-source nodes, the sum ...
-2
votes
1answer
64 views

NP-Complete Proof of k sized common set

Input: A set $U= \{w_1, w_2, \ldots, w_n\}$, subsets $S_1, S_2, \ldots, S_m$ of $U$ and integer $k$. Question: Is there a subset with $k$ elements of $U$ which intersects of every $S_i$? Which ...
4
votes
3answers
67 views

If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$? [duplicate]

Given two increasing functions $f$ and $g$ with values in the natural numbers, is it always the case that either $f\in O(g)$ or $g\in O(f)$. If the statement is true, then can anyone provide a ...
6
votes
3answers
568 views

Can a Minimum Possible Efficiency be proven?

Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be? For example, lets take the problem of sorting an array. Many of the ...
2
votes
2answers
130 views

Direction of restriction for NP hard proves

I have a very silly question, as I am reading through all the proofs showing a problem is NP hard, one of the techniques is by showing an already-proven NP complete problem is a special case for that ...
1
vote
0answers
85 views

Proof of NP-completeness of a special case of longest-path problem

Problem: Longest Path Input: undirected graph $G= (V, E)$ Question: is there a path with length at least $\frac{|V|}{4}$? I know that in order to prove the simple version of $k$ longest path, we ...
1
vote
0answers
54 views

Maximum flow problem with non-zero lower bound

Given $G = (V,E )$ a directed graph, if $ X \subseteq V $ we write $$\begin{align*} \delta ^{+}(X) &= \{ xy\in E \mid x \in X, y\in V - X \} \\ \delta ^{-}(X) &= \delta ...
0
votes
0answers
51 views

Union, Intersection, Difference, etc. of different types of languages

I am preparing for a competitive exam (GATE) in which questions are asked in Automata about operations among different types of languages. For example, If $L_1$ is recursive & $L_2$ is ...
0
votes
1answer
53 views

Prove that $\neg 0 = 1$

Starting from this definition https://en.wikipedia.org/wiki/Boolean_algebra_%28structure%29#Definition, is the following a valid proof that $\neg 0 = 1$? Instantiate a ∨ ¬a = 1 with a:=0 to get 0 ∨ ...
2
votes
1answer
55 views

Greedy proof: Correctness versus optimality

I am really confused after surveying a bunch of material online about correctness versus optimality proof for greedy algorithms. Some website even uses both correctness and optimal in the same ...
0
votes
1answer
35 views

Unclear about proof for unique MST given graph G with distinct weights

http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/mst.pdf I have some trouble understanding the proof above. I understand that we assuming two MSTs, T and T', and an edge e that is the ...
1
vote
2answers
122 views

How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?

I'm so bad at solving the problem of the type: "If $A$ is an NP-complete problem, $B$ is reducible to $A$, then $B$ is..." That I have to come here and ask these silly questions each and every ...
2
votes
1answer
48 views

Picking an $m$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $x_i$ is an element of the list $[x_1,x_2,…,x_n]$

I've got the following problem: Tommy has a toy consisting of wooden posts and in each move he can either hit one post (which decreases its height by 1) or pull out a post (which increases its height ...
4
votes
6answers
1k views

How is it valid to use oracles in mathematical arguments?

Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle". Thus, Oracles do not exist almost by ...
1
vote
1answer
24 views

Why does the principle of locality of computation not relativize?

Although I have trouble understanding oracle TMs, I appreciate that non-relativizing techniques will be needed to resolve P vs. NP (as well as most other open problems in TCS). However, one of the ...
3
votes
1answer
112 views

Why are non-relativizing proofs preferred to relativizing ones?

I apologize, but even after these two other posts: here and here I'm still having trouble understanding oracle TMs and relativization. This question comes at the issue from a different angle: Why ...
0
votes
1answer
55 views

Proof of equivalence of regular expressions (0 + 1)(0 + 1)* and (0 + 1)*(0 + 1)

How would I prove that the regular expressions RS and SR where R = (0 + 1) and S = (0 + 1)* are equivalent? The '+' sign represents union of two regular expressions and two expressions RS are ...
-1
votes
1answer
81 views

Proving correctness of a CFG by induction on length of strings generated [duplicate]

Consider the following grammar with starting symbol of $S$. $$S \rightarrow 0S11\;|\;S1\;|\;0$$ Let $L = \{0^i1^j:\; \ge 1\; and\; j \ge2i-2\}$ . Give a formal proof of the following claim : For all ...
2
votes
1answer
232 views

Proving Linear Time Temporal Logic formula □ ◊ f ⇔ ◊ □ f

I am new to this topic, Linear Time Temporal Logic and I am trying to prove this equivalence -- $\Box\Diamond f \Leftrightarrow \Diamond\Box f$ This is my take -- Basic definitions: $(\sigma, j) ...
0
votes
1answer
59 views

How do I use induction to show that the language of a grammar is contained in a given set? [duplicate]

Given that I have the grammar $\qquad\displaystyle G_1 = (\{a, b, c, d\}, \{S, X, Y \}, S, \{S → XY, X → aXb, X → ab, Y → cYd, Y → cd\})$, how am I supposed to prove that $\qquad\displaystyle S(G1) ...
2
votes
1answer
121 views

How can I make sense of amortized accounting method?

Amortized accounting method has to be one of the most abstract analysis technique I have ever seen in my life (maybe aside from the potential method which I haven't read). In the example of the Stack ...
2
votes
1answer
43 views

Proof that a node N balanced binary search tree has $2^i - 1$ children where $i$ is the position of the first 1-bit in N, starting from 0

I was binary indexed trees and I came across this article. One part of the justification was the following: Given that the (binary search tree) tree is perfectly balanced, a node N will have ...
0
votes
1answer
54 views

Understanding a proof in the sweep line algorithm when finding all line segment intersections

You have a set of line segments and you want to find all intersections. First sweep line approach: Use a priority queue Q for the events as they come, where each ...
2
votes
1answer
63 views

Show that the string $( [ ) ]$ is not in a Dyck language

I think I understand why the string $( [ ) ]$ is not in a Dyck language. In my words, D2* is all the dyck words of 2 parentheses. From the definiton of $D2*$, every words must have exactly 2 ...
13
votes
3answers
2k views

Is there an algorithm that provably exists although we don't know what it is?

In mathematics, there are many existence proofs that are non-constructive, so we know that a certain object exists although we don't know how to find it. I am looking for similar results in computer ...
0
votes
0answers
26 views

Proof of the base case of Big Theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. a and c are positive constants. $T(n)=a$, if $n=2$ $T(n)=2T(n/2)+cn$ if $n>2$ Use induction to prove that ...
1
vote
1answer
90 views

Proof of big theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove ...
1
vote
1answer
116 views

Not understand exchanging argument proof for optimal prefix code

I am currently reading the Algorithm Design textbook by Kleinberg and Tardos and I am having difficulty understanding a proof using an exchange argument Statement: A binary tree corresponding to the ...
0
votes
0answers
105 views

Proof by induction for a splay tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay ...
3
votes
1answer
54 views

Using induction to prove transition states are the same

Suppose that you have a DFA $M=\left(S,\Sigma,s_0,\delta,{s_f}\right)$ with $s_f\neq s_0$. Suppose further that, for all $a\in\Sigma$, $\delta\left(s_0,a\right)=\delta\left(s_f,a\right)$. Show that ...
1
vote
2answers
43 views

Asymptotic Proofs - BigOh/BigTheta

This is not homework, but from a past exam. I do not know how to solve this one at all. Can anyone please take the time and show me how to do these? Thank you. Prove that $5^n \in O(6^n)$, but ...
0
votes
0answers
36 views

How to prove a CFG is equivalent to a language [duplicate]

I have to prove the following statement: Prove that $\{0^m1^n | 0 ≤ m < n\}$ is the language generated by $S \rightarrow 0S1| A$ $A \rightarrow 1A | 1$ I can clearly see that the ...
0
votes
0answers
15 views

When proving a problem is NP-C, how do I select another NP-C problem for the transformation? [duplicate]

I'm taking an algorithms course in which we are discussing proofs that problems are NP-Complete. Our proofs usually take the form: Given a problem $\Pi$, 1. Prove that $\Pi$ is NP. 2. Select an ...
1
vote
1answer
55 views

How to prove strict space lower bounds using crossing sequences in Turing machines?

I understand the notion of crossing sequences when talking about time, however how are they used to actually prove strict lower bounds for some decision/search problems? For example, suppose that you ...
2
votes
1answer
76 views

Is an algorithm in pseudocode a reasonable way to establish complexity?

We define the language $$ L = \{a^nb^n : n\geq0 \} $$ and we want to prove the following $$ L = \mathrm{DSPACE}(\log n)\,. $$ So we have to prove that by using $\log n$ space on the work tape of ...
6
votes
1answer
94 views

Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?

The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup ...
-1
votes
1answer
46 views

Relationship between an NP-hard problems with the subsets of them (part 2)? [duplicate]

I asked two questions about NP-hard problems here Relationship between an NP-hard problems with the subsets of them? and here Does this manner of proof for being NP-hard is true? but unfortunately ...
1
vote
1answer
36 views

How do I solve interdependent recurrence relations?

I have three functions with values given as $$\begin{align*} P(0) &= 0 \quad & P(i+1) &= 5M(i)\\ M(0) &= 1 \quad & M(i+1) &= R(i) + 2P(i)\\ R(0) &= 3 ...
0
votes
2answers
67 views

Hoare Calculus Incorrect Assignment Axiom

I'm currently preparing for an exam and recently came across the following exercise and would like to know whether my solution would be correct. Exercise: Prove that the following axiom is not ...
1
vote
1answer
104 views

What is the min # of moves to sort an array from 1 to n?

Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to any place you want (insert to any place, not swap). Prove ...
5
votes
2answers
233 views

Direct NP-Complete proofs

I'm just starting to learn about NP-completeness. While I understand that reducibility plays a key role in this, I'm astonished how few problems I've been able to find who's proof that they are ...