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
0 votes
1 answer
54 views

Distinct edge weights assumption in second best MST algorithms only updating an edge in MST

In a CP-algorithms wiki Second Best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor: Let  $T$  be the Minimum Spanning Tree of a graph $G$ . It can be observed, that the second best ...
Kenneth Kho's user avatar
0 votes
0 answers
19 views

Proving Optimal Greedy Algorithms [duplicate]

How is the best way to go about proving that a greedy algorithm is optimal, inductive vs contradiction, are there parts in the proof that are key to include. I did not feel that the lesson I was ...
James's user avatar
  • 1
-2 votes
0 answers
45 views

struggling to prove the C-competitiveness of MTS

i need to show that if a MTS algorithm α is C-competitive against sequences of elementary cost vectors, then its C-competitive against any sequence of (non-negative) cost vectors. i tried to describe ...
amy's user avatar
  • 1
1 vote
1 answer
78 views

Amortised cost - transferring tokens

I'm trying to solve a problem from one of the older exams. Question: There's an infinite, one-dimensional board, with fields numbered consecutively $\ldots, -2, -1, 0, 1, 2, \ldots$ A move in the ...
Michał's user avatar
  • 113
1 vote
0 answers
33 views

Understanding line in Ramsey's Theorem proof

The following is from lecture notes for Concepts in Mathematics from CMU (William Gunther): I am confused about the bolded sentence in the last line quoted here: Theorem 4 (Ramsey's Theorem). For any ...
Flying Spaghetti's user avatar
3 votes
0 answers
73 views

Proof about Existence of Stable Matching

I've read the stable matching chapter in Kleinberg and Tardos's Algorithm Design and was wondering how one can show whether a stable matching under a given set of constraints exists. K&T introduce ...
Import Accelerate's user avatar
-1 votes
2 answers
219 views

Is the time complexity of a loop that simultaneously increments and multiplies $O(\log_k n)$ when $k = 1$?

Is the time complexity of for(int i=0;i<n;i++){i*=k;} $O(\log_k n)$? The problem is number 8 from GeeksForGeeks: https://www.geeksforgeeks.org/practice-...
HereToTryHelp's user avatar
0 votes
1 answer
30 views

Does Cutting Planes solve Pigeongole Principle for holes of different sizes?

Suppose a problem: Given $n$ pigeons and $m$ holes of sizes $b_{i\le m}$ decide if you can put all pigeons in given holes. It's possible to find a refutation of size $\mathcal O(n^2\log^2 n)$ of ...
rus9384's user avatar
  • 1,600
1 vote
2 answers
127 views

Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem

I've come up with a greedy algorithm proof for the minimum denominations problem, and I'm curious if someone can verify the correctness of the proof for me. I have simplified the problem by ...
Gary Drocella's user avatar
0 votes
0 answers
9 views

Turring Machine Variant and Equivalent Traditional [duplicate]

Turing Machine where instead of having a set of final states F it has: A designated final state qaccept which exists in Q set of states. Upon being in this state, it halts, and accepts the input. A ...
bruh's user avatar
  • 1
1 vote
2 answers
83 views

Union of non regular and regular language

So I have a regular language L and a non-regular language L' and i want to proof wether the union of both is regular or not. Since I found counterexamples for both cases I want to look at more ...
Theorynoob's user avatar
1 vote
2 answers
246 views

Trying to give a proof about graphs. Having a hard time giving proof for Kruskals algorithm. Can you check my answer?

Question: Let G(V, E) be an undirected connected finite graph with the weight function w : E → R+. Let T be a minimum spanning tree of G. Prove that there exists a run of Kruskal’s algorithm that ...
kjkjkjkjkj's user avatar
0 votes
2 answers
37 views

Can proofs by induction be achieved by defining a recursive function between two recursive objects?

I have two types of objects, X and Y, each are recursive structures, and contain different structures sets of tuples containing sets.. etc. The number of elements in X and Y are is the same. I need to ...
newlogic's user avatar
  • 165
0 votes
0 answers
32 views

Confused about decomposition in Context Free Pumping lemma

I am trying to decide whether the following language is context free: $$L = \{ a^nb^{3n}c^n \, | \, n \geq 0 \} $$ Assume $L$ is context-free. Let $p$ be the pumping length given by the Pumping Lemma. ...
Priit's user avatar
  • 1
0 votes
0 answers
18 views

prove that the language L = { ww | w ∈ {a,b}* } is not context free [duplicate]

I came across this question presented in a past exam. I can see why the language is not context free (you can't know what the first w is, hence you are not able to duplicate it, I hope it makes sense),...
pezbecoding's user avatar
0 votes
1 answer
412 views

Proving the correctness of a greedy algorithm for the Circular Scheduling Problem

Consider the following variation on the Interval Scheduling Problem You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each ...
Tejas Anand's user avatar
0 votes
1 answer
85 views

PSPACE≠co-NP?Is the statement true?

Is the statement in question true? how can i prove it formally? I know that PSPACE=CO-PSPACE and NP ⊆ PSPACE and CO-NP ⊆ CO-PSPACE
user161390's user avatar
1 vote
1 answer
52 views

Greedy algorithms criterion/ intution

Can anyone please explain (not just through examples) that why does the greedy approach does not work in this case? Or more generally, is there any particular condition under which only the greedy ...
green_32's user avatar
  • 113
25 votes
13 answers
6k views

False proofs that look correct

I remember seeing a list of False Proofs when I was taking Discrete Maths and I found it to be very interesting and also helpful. So, if anyone knows some common proof mistakes students make or some ...
proof-of-correctness's user avatar
0 votes
0 answers
21 views

What would be the logical requirements on a language, in order to do direct meta-programming in it?

I am motivated by the idea of generating “words” or “pairs” in a programming language or set of commands. For example, consider any arbitrary REST API. Beyond requesting the original URL endpoint, ...
D J Sims's user avatar
1 vote
0 answers
44 views

Is this a correct way of using structural induction to prove type uniqueness?

I was reading the book "Types and Programming Languages" by Benjamin C. Pierce, paying attention to proofs so I could learn proof techniques. In the parts discussing the simply typed $\...
alim's user avatar
  • 994
1 vote
0 answers
33 views

Random process on ternary string

Given a ternary string S of length N, do the following: Find the first strictly decreasing pair of digits. Randomly change one of the digits in the pair to another value. The string is circular (i.e ...
Duc-Anh DO's user avatar
0 votes
1 answer
36 views

Proof techniques and correctness proof of minimum cost to make string equal

I've lately been struggling to write correctness proofs for various algorithms, even when it is "obvious" to me that the algorithm works and is correct. For example, take the following ...
user308485's user avatar
0 votes
0 answers
64 views

Proving that the polish notation has unique readability

I am familiar with the polish notation when it comes to algorithmically reading phrases, but I am having a hard time proving the following exercise: K is a function so that 1) $K(*)$ is an integer if ...
Tita's user avatar
  • 225
0 votes
0 answers
85 views

How to prove (L+M)* = M*.(L.M*)*

Question is to simplify (LM*)* and I couldn't figure out a way to simplify it. Since (L+M)* = M*.(L.M*)*, I guess we can say that it cannot be simplified more. So how do we prove that they are the ...
mark's user avatar
  • 67
0 votes
0 answers
107 views

How to prove the performance ratio of the approximation algorithm of maximum clique is unbounded

Consider the following approximation algorithm for the problem of finding a maximum clique in a given graph $G$. Repeat the following step until the resulting graph is a clique. Delete from $G$ a ...
RJ94's user avatar
  • 1
0 votes
0 answers
33 views

Show that Language L = { <M> | M is a TM and {b}* ∩ L(M) ≠ ∅ } is recursively enumerable?

I'm not sure how to show that the language L = {M | M is a TM and {b}* ∩ L(M) ≠ ∅ } is recursively enumerable. I understand that if there is a DTM that accepts every word of the given alphabet, it is ...
Ashman's user avatar
  • 1
1 vote
1 answer
165 views

(Directed) Graphs: Minimal Vertices Subset With No Outgoing Edges

I've been trying to study some graph algorithms and, as part of it, prove a bunch of graph theorems in order to practice my ability to do theoretical work with graphs. Specifically, I've been trying ...
Shay's user avatar
  • 113
0 votes
0 answers
47 views

Proof that Path with admissible edges is shortest

Consider an unweighted and directed graph G(V, E). Suppose, for every vertex v ∈ V we assign a vertex label y(v). We say that the vertex labeling is valid if for every edge (u, v) ∈ E that is directed ...
Jason Ron's user avatar
0 votes
1 answer
34 views

How can it be formally proved that $f \in O(⌊f ⌋)$

I'm trying to prove that $f \in \mathcal{O}(\lfloor f \rfloor)$ given that $\forall m \in \mathbb{N}, f(m) \geq 1$ Here's what I've thought of so far, we can set C = 10 and k = 1 and somehow prove ...
Raghav Sinha's user avatar
0 votes
5 answers
2k views

Does contradiction definitively prove nonexistence

It is common to have proofs that use contradiction to show that some language is undecidable in computability theory. An example proof can be seen in 4.2 Undecidability “Introduction to the Theory of ...
Dereference's user avatar
0 votes
1 answer
322 views

Proving why decreasing an edge weight in a graph may change it's MST by one edge

I'm working on understanding graphs and graph algorithms. The problem is from: https://courses.engr.illinois.edu/cs374/fa2020/labs/sol/lab_12_b_sol.pdf (Q 1.D) Describe an efficient algorithm to ...
DarkCave's user avatar
-2 votes
2 answers
234 views

Halting problem disproof

Introduction This is a heavily updated question I have asked on this forum previously. I have understood and corrected the earlier errors and mistakes I made, and after doing that it still seems I ...
Mercury's user avatar
  • 107
1 vote
2 answers
68 views

"Largest set" in coinductive definitions

In several explanations of coinductive definitions (for example, in the answers to What is coinduction?), we're told that while an inductive definition gives us the smallest set with a specified set ...
N. Virgo's user avatar
  • 966
-4 votes
5 answers
417 views

Halting problem logic must be wrong

I think that I have found an issue with the proof of the halting problem, which would cause the entire proof to be invalid. To ensure I understand, here is Turing's proof of the halting problem being ...
Mercury's user avatar
  • 107
3 votes
0 answers
40 views

Can fine-grained hardness be proved directly from classical hardness (e.g., $\sf P \neq NP$) in some way?

I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph ...
Heda Chen's user avatar
  • 311
-2 votes
1 answer
57 views

How to use Pumping Lemma $L = \{ wsw \mid w \in \{0,1\}^*, s \in \{2\}^* \text{, and } |w| = 2 \cdot |s| \}$?

I'm trying to use the Pumping Lemma to prove that $L = \{ wsw \mid w \in \{0,1\}^*,\ s \in \{2\}^*\text{ and } |w| = 2\cdot|s| \}$ is not a CFL.
ZisIzHell's user avatar
2 votes
1 answer
210 views

How to evaluate the tightness of a bound on a function?

I recently submitted a paper where in part of the paper I derived a bound on a function (note it is an upper bound). The benefit of the bound is that it is much less complex to compute in contrast to ...
Ralff's user avatar
  • 163
2 votes
0 answers
248 views

How would I prove that the algorithm to find the k-cores graph, produces a maximum size of vertices?

I came across this simple algorithm for finding a k-core of a graph, but every paper I read gives this notion of being maximal without proof, and I'm wondering how I might prove it. So a k-core of a ...
universityofwashingtoncoder's user avatar
13 votes
5 answers
5k views

Proving Equivalence of Two Regular Expressions

Consider the regular expressions $(1+01)^*(0+\epsilon)$ $(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$, where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
Keio203's user avatar
  • 257
1 vote
0 answers
80 views

Proof for Queue in BFS consists of vertices of distance k and k+1

For any vertex v reachable from s, BFS computes a shortest path from s to v (no path from s to v has fewer edges). In order to prove the above proposition, The author of the book has stated that we ...
Krishna M.V.'s user avatar
0 votes
2 answers
113 views

Irregularity of $\{a^{b+cd} : d \in \mathbb{N}\}$

I was solving some basic problems about the theory of machines and automata. The topic was about pumping lemma, but I could not solve the below question and prove that it is not regular. $$L=\{a^{b+cd}...
Aylin Naebzadeh's user avatar
2 votes
2 answers
121 views

having trouble understanding the proof of regular expression identities $(u + v)^* = (u^*v)^*u^*$

I am having trouble understanding the proof given below: \begin{align} (u \cup v)^* &= (u^* \cup v)^* \\ &= u^*(u \cup v)^* = (u\cup vu^*)^* \\ &= (u^*v^*)^* = u^*(vu^*)^* \\ &= (u^*v)...
Lucas Timothy's user avatar
2 votes
1 answer
708 views

How to prove cycle sort has the minimum swap times?

Copy from Wikipedia Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any ...
Voyager's user avatar
  • 187
2 votes
2 answers
130 views

How do I prove the following invariant of this program?

I have been studying different topics within the realm of concurrent programming and came across "Lamport's bakery algorithm" which is based on the original version of the bakery algorithm ...
NoName123's user avatar
  • 171
2 votes
1 answer
177 views

Language of Turing Machines that only accept their own encodings

Is the language $L = \{\langle M\rangle|L(M)=\{\langle M\rangle\}\}$ recursive? I've been trying for hours to find a way to prove or disprove that it is. My first attempt was to show it wasn't ...
Konsti's user avatar
  • 21
0 votes
1 answer
26 views

Termination condition for max of array using divide and conuqer approach

I want termination proof of divide and conquer approach to find max of array,I want equational proof in form of lemma.Below is my attempt.I have got accepted everything in dafny ,it is only pointing ...
user avatar
0 votes
1 answer
96 views

BST subtree value range

Suppose we have a node x in BST, and let max and min be the largest and smallest keys in the subtree rooted at x respectively. Prove that for any node n outside this subtree, the key of n is either ...
r_d26's user avatar
  • 9
0 votes
1 answer
87 views

Isabelle (rule disjE) disjunction elimination rule

...
Ricardo Boza's user avatar
0 votes
3 answers
1k views

Understanding proof that no DFA can recognize L with fewer than 2^k states

Let Σ = {a, b} and L = {ww | w ∈ Σ∗ and w is of length k}. Show that for each k, no DFA can recognize L with fewer than 2^k states. What I understand is that we prove this by contradiction. Assume ...
Uzair Siddiqui's user avatar

1
2 3 4 5
14