Questions tagged [proof-techniques]
Questions about general methods and techniques for proving multiple theorems. When asking about the proof of a single statement, use tags relating to what the proof is about instead.
693
questions
2
votes
1
answer
81
views
How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?
Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each ...
- 319
1
vote
1
answer
171
views
How to correctly describe this action, deleting an edge that "shortcut" some vertices
Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below:
1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in ...
- 13
0
votes
0
answers
160
views
proving DFA stuck
This DFA fulfills:
Define a function $diff: \{0,1\}^*\to\Bbb Z$, for $w \in\{0,1\}^*$, $diff(w)=($# of 1's in $w)- ($# of 0's in $w$).
Thus, $diff(\epsilon)=0$; $diff(0)=−1$; $diff(1)=1$.
Let $L = ...
0
votes
0
answers
37
views
dfa subtract multiple of 3 [duplicate]
Define a function 𝑑𝑖𝑓𝑓 ∈{0,1}→ℤ so: for everything w ∈{0,1}, diff w = # of 1's in w- # of 0's in w.
Thus:
𝑑𝑖𝑓𝑓 𝜀=0;
𝑑𝑖𝑓𝑓 0=−1;
𝑑𝑖𝑓𝑓 0=−1;
Let 𝐿 = {𝑤∈ {0,1} * | 𝑑𝑖𝑓𝑓 𝑤 = 3𝑚 ...
0
votes
2
answers
1k
views
prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves
I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction
*Edit: my professor had a significant typo in this assignment, I have attempted ...
- 205
1
vote
0
answers
77
views
Can we ignore the postcondition in the Hoare conditional rule when there is a return statement?
I'm proving the correctness of naive string matching using Hoare logic. I have the following pseudocode:
...
- 215
1
vote
4
answers
2k
views
Deriving lower and upper bounds for T(n) = T(n-1) + T(n-2) + 10
The solution is to find the upper and lower bounds from:
2T(n-2) < T(n) < 2T(n-1) + 10
So I have to find
...
- 11
2
votes
1
answer
60
views
Must a function in lambda-calculus which inputs a boolean function be defined in a certian way?
This question is my best attempt to get at a more general question about what one can get from terms in the lambda calculus.
Using the church encoding, we define booleans by
$\texttt{true} = \lambda ...
- 319
3
votes
1
answer
54
views
Finding maximum takes at least $\lceil n/2 \rceil$ comparisons
We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$.
I want to prove that finding the maximum in $A$ (that is, outputting the index ...
- 33
3
votes
1
answer
1k
views
Union of infinitely many regular languages [duplicate]
I need to prove or disprove the following statement.
If $A_n ⊆ \Sigma^*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular.
I know that if two languages ...
0
votes
1
answer
862
views
Proving the singleton language {x} is regular for all x ∈ Σ*
So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would ...
2
votes
2
answers
522
views
Proving that Every Full Prefix-Free Language is Maximal
I'm practicing a problem where I need to prove that every full prefix-free language is maximal.
I know a prefix-free language A is maximal if it is not a proper subset of any prefix-free language, ...
- 131
0
votes
1
answer
808
views
Proving that A(B ∩ C) ⊆ AB ∩ AC
A(B ∩ C) = { UV | U ∈ A, V ∈ B and V ∈ C } for the left part.
ΑΒ = { UV | U ∈ A, V ∈ B },
ΑC = { UV | U ∈ A, V ∈ c },
AB ∩ AC = { UV | U ∈ AB and AC, V ∈ AB and AC } for the right part.
How can I ...
- 103
1
vote
1
answer
465
views
Proof of an Infinite Binary Sequence
I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}*
such that ww is a prefix of S.
I need to prove that if ...
1
vote
4
answers
100
views
Proving B* = B on a given set
I have the set:
B = {x ∈ {0,1}* | there is an equal number of 0's and 1's in x}
and therefore,
B* = {e,01,10,0011,0101,0110,1100,1010,1001,....etc}
I need to either prove or disprove that B*=B
I ...
- 11
1
vote
0
answers
76
views
Sum of long geometric progression [closed]
Finding sum of a geometric progression is simple when we just need to report the sum,
but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me.
I have a ...
- 11
2
votes
0
answers
77
views
Can Pareto Optimality be compared to Nash Equilibrium?
Given a state $s$, and a value function $v^i$ that determines the expected payoff for the i-th agent in that state, can the two definitions below, one of Nash equilibrium and another of Pareto ...
- 121
1
vote
0
answers
1k
views
Proof that G is a Tree After DFS and BFS form the same tree T [closed]
Let G be a connected, undirected graph containing some vertex s. let's say that BFS and DFS are both run on G starting at s and that the breadth first search and depth
first search ...
- 81
1
vote
1
answer
1k
views
Prove Halting on all Inputs is not in RE simulation
I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine ...
- 13
1
vote
0
answers
203
views
Could you show the intractibility of SAT by showing that the number of variables contributing to an arbitrary unsatisfied clause is not constant? [closed]
Preface: This is not an attempted proof at P vs NP
Starting with some CNF Boolean expression ϕ, by the rules of logical disjunction, a clause is only unsatisfied if each of the literals in it are ...
- 111
-1
votes
1
answer
176
views
Why proving the solution of a problem is polynomial time is sufficient enough to say that it is a NP prolbem? [duplicate]
Why proving that we can verify the solution of a problem is polynomial time is sufficient enough to say that the problem is nondeterministic polynomial time? Please note: this is not a question on how ...
- 81
2
votes
2
answers
85
views
Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$
How can I prove that $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$ is decidable ?
I know that $EQ_{CFG} = \{⟨G, H⟩ \mid \text{$G,H$ are CFGs and $L(G) = L(H)$}\}$ is not.
- 169
2
votes
4
answers
214
views
1
vote
2
answers
142
views
How to generate an instance for an NP_hard proof, where each element has two inputs?
I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (...
- 159
0
votes
1
answer
52
views
Is this a valid induction proof example ?
Learning induction proof now, found a "simple" example, which is a bit confusing to me (not sure if it is a valid example). If so, why the IH(
suppose a root of rank k has at least $2^k$ vertices in ...
- 227
2
votes
1
answer
1k
views
Turing machine with semi infinite tape - Prove by construction
I'm studying constrained Turing Machines.
There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 ...
- 123
1
vote
1
answer
2k
views
Trouble understanding this proof about the minimum number of states of a deterministic finite automaton
So I was browsing online looking for the general structure to proving a DFA has a minimum of $n$ states for some $n$ and most of them use contradiction. However, I'm having a hard time understanding ...
- 13
0
votes
3
answers
737
views
Intuitive proof for a tree with n nodes, has n-1 edges
I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.
- 31
2
votes
3
answers
667
views
Alternate proof of the Caro-Wei theorem for lower bounding the independence number
Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
- 123
2
votes
1
answer
255
views
Proving problem NP-completeness [duplicate]
I am studying computational complexity and i am trying to solve this problem.
We are given a (non-bipartite) complete graph:
G = (V, W, E)
where the vertices can be divided in two classes V and W ...
- 23
4
votes
2
answers
238
views
Proving a value is the result of the execution of an algorithm
Assuming an algorithm $A$ known to both Alice and Bob.
Alice runs the algorithm and gets a result $R$.
How can Alice prove to Bob that $R$ is the result of the execution of $A$ and not some random ...
- 43
1
vote
1
answer
390
views
Proof for Turing Machines being able to simulate any algorithm in the same time complexity
I have always read that Turing machines can simulate any algorithm, without changing the time complexity of the algorithm, and hence it is easier to study the Turing machine equivalent of the ...
- 213
1
vote
1
answer
189
views
Proof By Contradiction - Hamiltonian Paths and Cycles
Was hoping if anyone had any way to prove the following claim using proof by contradiction
Let $G = (V, E)$ be a simple graph with at least one vertex, and let $G'$ be the graph formed by adding a ...
- 11
0
votes
1
answer
91
views
Showing $2^x$ is a lower bound
How do I show that $2^x - x^2 \in \Omega(2^x)$?
Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.
I worked around a bit with ...
- 178
2
votes
1
answer
216
views
How do we know that Icosoku always has solutions?
This is a continuation of a question I asked here. The puzzle Icosoku is now described by Wikipedia as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-...
- 301
4
votes
4
answers
4k
views
Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?
I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half ...
user82869
0
votes
1
answer
31
views
There could not be an edge from u to v in a DAG, if w is before v in a topological order
I am trying to prove that given a DAG. There exists a valid topological ordering that has v in front of u iff there is no path from u to v. The proof is related to the fact that reverse DFS post ...
2
votes
0
answers
97
views
Challenging exercises for proof correctness [closed]
I would like to know where I can find challenging exercises that ask to prove the correctness of an algorithm.
The invariant of most of the exercises I’ve found on the internet are quite easy (...
- 21
1
vote
1
answer
404
views
lower bound proof with adversary argument
We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full ...
- 319
2
votes
1
answer
107
views
How to reduce a problem?
I am a bit confused on how to reduce a problem. I'll give an example:
Let's say there is a problem called HALTEMPTY and we know it is undecidable.
$HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ...
- 23
6
votes
1
answer
881
views
Undecidable problem intersection of two DCFL languages is DCFL?
We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an ...
- 201
1
vote
0
answers
323
views
How to prove that the predecessor of each node in Dijkstra form a tree?
Prove that the array prev[.] computed by Dijkstra’s algorithm, the edges (v, prev[v])
for all v ∈ V , form a tree
In order to prove this I used induction.
Lemma :...
- 11
2
votes
2
answers
152
views
How to Apply Elementary Axioms from Kleene Star to an Inequality
Axioms For *
\begin{align}
1 + aa^* &\leq a^* \\
1 + a^*a &\leq a^* \\
b + ax &\leq x \to a^*b \leq x \\
b + xa &\leq x \to ba^* \leq x \\
\end{align}
Elementary Results
\begin{...
- 37
7
votes
3
answers
4k
views
Prove that A** = A*, where A is a language over Σ*
Let $\mathcal A$ be an arbitrary language over $\Sigma^*$
Proof.
To prove, $\mathcal A^{**} = \mathcal A^* $
$\mathcal A^{**} = \left( \mathcal A^0 \cup \mathcal A^1 \cup {...} \cup \mathcal A^n \...
- 85
3
votes
1
answer
55
views
Any finite Graph G with all V have at least degree of 2, is it true that every vertex is necessarily contained IN a cycle?
As title, (note: this questions is asking weather or not all vertices are contained IN a cycle not asking if the G contains a cycle.
My attempt is that:
So this graph would be an counter example that ...
user94430
3
votes
1
answer
273
views
Relating a proof to a Haskell program
I am trying to relate the following integer square root theorem
$\forall x: \mathbb{N}, \exists y : \mathbb{N}((y^2 \leq x) \land (x < (y+1)^2))$
and its proof to its role as a specification of ...
- 339
8
votes
1
answer
330
views
Is it possible to simulate a fair coin with a finite number of tossing of a biased one?
It is a classic problem to simulate a fair coin with a biased one.
According to Fair Coin (wiki),
John von Neumann gave the following procedure:
Toss the coin twice.
If the results match, start over,...
- 9,551
0
votes
1
answer
128
views
Does indirect diagonalization a relativize technique?
My main question is can with R.kanon , Fortnow ,... technique that shows lower bounds for SAT seperate P and NP ?
Baker-Gill-Solovay showed that $P?=NP$ could not be solved with relativization. Does ...
- 537
4
votes
1
answer
72
views
Removing arithmetic within recurrences
A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works.
Say, for $T(n) = T(\lceil n/5 \rceil + 36) + n \log n$
...
- 203
2
votes
1
answer
215
views
How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation?
How to prove that a string, s is made up of n > 1 subsequences occurring some arbitrary number of times using concatenation ...
- 23