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.

Filter by
Sorted by
Tagged with
1
vote
1answer
49 views

Why discriminate the base case allows me to complete the induction proof?

I have a successful completed proof which used induction. but I essentially proved the goal on the base case by tactic discriminate. Why is this induction proof ...
1
vote
1answer
34 views

Converse proof for random coding capacity of AVC

I want to see the converse proof for the random coding (shared randomness) capacity of AVC. All I can find online is Csiszar Narayan's AVC paper which looks at deterministic coding. Further, the proof ...
0
votes
2answers
59 views

Are different assignments allowed for the implication graph proof of 2-SAT being in P?

One proof for $2-SAT$ being in $P$ uses the implication graph, i.e. one creates 2 vertices per variable $a$, one for each possible literal ($a$ and $\neg a$). One then adds 2 arcs per clause $(a \lor ...
4
votes
0answers
230 views

Can every sentence of first-order logic be converted into an equisatisfiable equation in Boolean algebra?

There may be some theoretical literature, unknown to me, that addresses this question. If possible, I would like a practical approach to this problem. My attempt involves the use of an equational ...
1
vote
0answers
41 views

why is behaviour of simpl differ so much after a commutative operation and how to inspect simpl?

In Coq, while trying to prove a lemma mult_n_Sm for mult_comm, I have this equation in a proof: ...
3
votes
1answer
36 views

Why isn't plus_assoc rewriting correctly?

First I have plus_assoc ready. Theorem plus_assoc : forall n m p : nat, n + (m + p) = (n + m) + p. for simplicity we omit the ...
0
votes
1answer
27 views

How do you prove these string/number radix encoding/decoding algorithms work?

A while back I learned of these great algorithms: ...
1
vote
2answers
64 views

Closed form of recurrence with two inputs

This question comes from a relatively simple coding challenge at Codesignal, but represents an interesting CS/math puzzle. The question states: "When a candle finishes burning it leaves a ...
4
votes
1answer
653 views

Is every unambiguous grammar regular?

While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language. But is there a regular language for every unambiguous grammar? How can I ...
0
votes
1answer
69 views

Hardness of maximizing difference of functions

Suppose that the problem of maximizing a real function $f$ over a certain domain $D$ is NP_HARD. What can be said about the problem of maximizing $f-g$, with $g$ being another function over $D$? Is it ...
1
vote
0answers
40 views

Constant in Substitution method for recurrence

The solution for solving the following recurrence with the substitution method involves adding the a constant inside the recurrence, which is confusing to me. This is question 4.3-2 in the CLRS ...
0
votes
1answer
60 views

Why doesn't diagonalization require taking a limit?

When we quantify infinite sums, we do so by taking the limit as $i$ goes to infinity. For example, we look at $\lim_{n\rightarrow \infty}\sum_{n\in \mathbb{N}}n$, and then we say that this diverges ...
1
vote
1answer
104 views

On the proof techniques of Udi Manber

I was familiar with the approach of first coming up with an algorithm, and then proving the loop invariant to come up with an algorithm as elucidated in CLRS (Introduction to algorithms, Thomas H. ...
0
votes
2answers
55 views

what is the relevance of computability when applying diagonallization?

When thinking about diagonalization, I've always glossed over whether or not the enumeration, or the diagonal is computable or not. When does it matter? Say for example, that have an enumeration of ...
1
vote
0answers
162 views

Understanding the proof of "DFS of undirected graph $G$, yields either tree edge or back edge" better with graph for each statement in proof

I was going through the edge classification section by $\text{DFS}$ algorithm on an undirected graph from the text Introduction to Algorithms by Cormen et. al. where I came across the following proof. ...
11
votes
12answers
8k views

Why are mathematical proofs so hard?

I am an electrical engineer and trying to make a transition into machine learning. I read in multiple articles that I have to learn data structures and algorithms, before this I have to learn about ...
1
vote
1answer
123 views

Difficulty in understanding a portion in the proof of the $\text{"white path"}$ theorem as with in CLRS text

I was going through the $\text{DFS}$ section of the Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding the $\Leftarrow$ direction of the proof of the white path ...
2
votes
1answer
172 views

Difficulty in understanding a statement in the proof of the correctness of $\text{BFS}$ algorithm as dealt with in CLRS

I was going through section of Breadth First Search of the text Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding a statement in the proof below which I have marked ...
1
vote
1answer
149 views

Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP

In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $n\times n\times n$ Rubik's Cube is an NP-complete problem. In the process, they must show that the ...
0
votes
1answer
85 views

Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

The following is the definition for Proximate Sorting given in my paper: An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array ...
3
votes
2answers
264 views

Difficulty in understanding the proof of the lemma : "Matroids exhibit the optimal-substructure property"

I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma ...
1
vote
1answer
80 views

Pumping Lemma for CFL - $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $

I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language: $$ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $$ I ...
2
votes
1answer
88 views

Recurrence relation for the number of "references" to two mutually recursive function

I was going through the Dynamic Programming section of Introduction to Algorithms (2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the context of assembly line ...
2
votes
0answers
56 views

In Universal Hashing- probability of poor performance is small and is the same for any set of keys of the same size

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following claim: Universal Hashing uses randomization.For the example of a compiler's symbol table, ...
1
vote
1answer
57 views

Need hint for bipartiteness proof

I am given a graph $G = (V, E)$ with $N$ connected components and $G^\prime = (V^\prime, E^\prime)$, where for each $v \in V$ there is $v_1, v_2 \in V^\prime$ and for each $(u, v) \in E$ there is $(...
0
votes
1answer
76 views

Difficulty in understanding few steps in the proof: "The class $\mathscr{H}_{p,m}$ of hash functions is universal"

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following excerpt regarding the said proof and the steps where I felt difficulty are marked with $\...
1
vote
1answer
177 views

Clarification of the proof involving the regularity condition in Master Theorem

I was going the text Introduction to Algorithms by Cormen et al. Where I came across the following statement in the proof of the third case of the Master's Theorem. (The Statement of Master theorem) ...
2
votes
1answer
39 views

Language of lists of words, not all of which are different, is not context-free

How do I prove that the following language isn't context-free using the pumping lemma? $$ L=\{w_1\#w_2\#\dots\#w_k \colon k ≥ 2, w_i \in \{0,1\}^*, w_i = w_j \text{ for some } i \ne j\} $$ I am having ...
1
vote
1answer
101 views

Proof that if P=PSPACE, RP=BPP

Like the title says. I can't figure out how to prove this. I think it probably has to do with the polynomial hierarchy collapsing but I'm not sure.
0
votes
1answer
216 views

Is the BPP class closed for union and intersection?

Just like the title says. I want to prove that given two languages $L_1,L_2 \in BPP$, $L_1 \cup L_2 \in BPP$ and $L_1 \cap L_2 \in BPP$
0
votes
1answer
47 views

Show that f(x,y)=x+y (with |x|=|y|) isn't a one way function

I have to prove that the function $f\colon \mathbb N × \mathbb N \to \mathbb N$ defined by $f(x, y) = x + y$ and $|x| = |y|$ isn't a one-way function. How do I go around doing that?
1
vote
3answers
78 views

Proving a solution for the $n$-Queens Puzzle

Given an $n$ x $n$ board, assume that $n \geq 5$ and that $n$ is not divisible by $2$ or $3$. Prove that the following positioning of $n$ queens $Q_0, Q_2, ..., Q_{n-1}$ works, i.e no two queens ...
0
votes
1answer
72 views

Semi-decidability of the language $\overline{L_{\epsilon}}$

Firstly consider the problem: given $L_H = \{R(M)w : M \in TM_0, w\in L(M)\}$ where $R(M)$ are encoded transitions of $M \in TM_0$. Assume for contradiction $\overline{L_{H}}$ is semi-decidable, then ...
1
vote
1answer
80 views

on coq: Why is the proof complete after proving only for one induction when we have more than one variable?

So I'm learning coq. And I came across the proof for associativity in addition forall (a b c : nat) Appearntly when we do ...
3
votes
1answer
77 views

How to prove that replacing a character in a string in both C and JavaScript is equivalent?

I would like to try some different proofs, specifically in proving equivalence of the implementation of some feature in two different programming languages (C and JS in this question). This is about ...
2
votes
1answer
87 views

Lambda calculus without free variables is as strong as lambda calculus?

First question: How would one prove that by removing free (unbound) variables from lambda calculus, and allowing only bound variables, its power is not reduced (it is still Turing-complete) ? Second ...
1
vote
1answer
60 views

Proving the pigeonhole principle in Cutting Planes

Exercise 3 from https://massimolauria.net/courses/2015.ProofComplexity/lecture6.pdf Consider the set of inequalities $x_i+x_j\leq1$ for $1\leq i<j\leq n$. Find a derivation of $\sum_{i=1}^n ...
2
votes
2answers
175 views

Double hashing constraints

For double hashing, we have some constraints on $h'(k)$ (1) It should never evaluate to 0 (2) It should be relatively prime to m How to show that all slots in an open addressing table will be ...
1
vote
1answer
73 views

Proving van Emde Boas recurrence

I have tried to solve the following question: van Emde Boas Bounds Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. Hint: consider the binary representation of $u$. ...
0
votes
2answers
78 views

How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $

I am trying to answer this question: $3x^3 +2x + 1$ is $ \omega(x \cdot \log x)$ My question is how to solve this question. Here is what I have tried so far: I applied the definition $3x^3 + 2x + 1 ...
4
votes
1answer
95 views

Why is $NP \subseteq P \implies NP^A \subseteq P^A$ false?

My question is about why does the result of Baker-Gill-Solovay not prove that $P \neq NP$. There have been several questions on this forum about this topic perhaps but I couldn't find my specific ...
1
vote
1answer
76 views

Checking whether union of two languages is regular

How to check if $L = \{c^ka^nb^n \mid k>0 \wedge n\geqslant0\} \cup \{a, b\}^*$ is regular ,where $L_1 = \{c^ka^nb^n \mid k > 0 \wedge n\geqslant0\}$ is clearly not regular and $L_2 = \{a, ...
2
votes
1answer
214 views

Proof of a greedy algorithm used for a variation of bin-packing problem

We are given an array of weights $W$ (all weights are positive integers), and we need to put the weights inside bins. Each bin can hold a maximum of Max_val, and each weight is at most Max_val. The ...
0
votes
1answer
137 views

Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$

I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it? ...
1
vote
0answers
34 views

Accessible CS Math Job [closed]

I am a CS undergrad and a huge enthusiast of pure math. I have been doing competitive programming and proofs for a while. My ambition is to become an academic in theoretical computer science. The ...
-1
votes
1answer
69 views

Merging $t$ arrays of size $t$ cannot be done in $O(t^2)$

Dr. John claims that he designed a comparison-based algorithm FastMerge that can merge $t$ arrays of size $t$ at most each in $O(t^2)$ time. In Dr. John’s own words, ”Given $t$ sorted arrays $B_1,B_2,...
1
vote
1answer
40 views

Parity of number of divisors

Im pretty new here. My question showing me an algorithm: TRUE_SEQ(A[1...n]) ...
1
vote
0answers
183 views

Combining TWO Monte Carlo algorithms to get a Las Vegas algorithm that solves the same problem

I came across a problem that I have no clue how to solve. Consider two Monte Carlo algorithms, called A and B that both solve the same problem. A is true-biased and t-correct, while B is false-...
4
votes
2answers
79 views

Prove that if we take all the edges in directed graph that are on some shortest path from 1 to N we will get a DAG

We are given directed weighted graph with edges having strictly positive weight(>0) with possibly some cycles with $N$ nodes and $M$ edges. Let's observe all the shortest paths from $1$ to $N$ in this ...
1
vote
2answers
278 views

Proof by contradiction for greedy algorithms

I'm having some difficulty understanding/being convinced the technique used to prove a greedy algorithm is optimal for the fractional knapsack problem. A proof by contradiction is used. I've never ...

1
2
3 4 5
13