Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
0 answers
27 views

Minimum expected number of path to cut graph problem

I came up with a problem but was unable to show the hardness of the problem (NP/#P/P-hard). The problem is as follows. Given a directed graph $G=(V, E)$, each edge will have a confidence score $c$. ...
sweet-potato's user avatar
-1 votes
1 answer
25 views

Show that it is Np-hard to determine whether a given graph has the crossing number k

I want to prove that this problem to find whether the crossing number of any given graph is K or not, is NP-Hard. I don't know how to do this. Can someone help me with this ?
Virar's user avatar
  • 1
1 vote
2 answers
31 views

Intuitive explanation/overview of non-looping non-termination proofs

Looping non-termination is intuitively easy to understand and demonstrate, by finding/showing a sequence of transformations that cycles back itself. Say, using the rewriting system: ...
2080's user avatar
  • 241
0 votes
0 answers
7 views

Load Balancing with No Overlap

Problem Suppose there are $n$ jobs $J_1, \ldots, J_n$ that need to be completed using $m$ machines $M_1, \ldots, M_m$. Each job $J_i$ consists of a set $S\left(J_i\right)$ of $k_i$ sub-chores $s_1, \...
cuppajoeman's user avatar
1 vote
1 answer
52 views

Prove maximum score is achieved by being greedy

I have a list of tokens T, of length n. Initially I have power p and a ...
rranjik's user avatar
  • 284
-3 votes
3 answers
60 views

Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$

Anyone please answer the question: Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$.
Ayush Verma's user avatar
-1 votes
1 answer
53 views

Proving tight bound Θ for worst-case running time of an algorithm without proving lower bound Ω

See this answer first: Proving worst-case running time is in $\Omega(n^2)$ Understanding the linked answer for insertion sort leads to the following statement. Prove that the statement is either ...
jam's user avatar
  • 13
2 votes
2 answers
94 views

can we computably list every primitive recursive function?

i have seen some articles where they use the diagonalization argument to prove the existence of non-primitive recursive functions. But this should only work if we can create an infinite list of every ...
Aditya Mishra's user avatar
3 votes
1 answer
45 views

Invariance Textbook Problem: Clarification Needed

I am currently reading Michael Soltys' Analysis of Algorithms (2nd Edition), and Problem 1.13 of the subsection titled Invariance reads: Let $n$ be an odd number, and suppose that we have the set $\{...
Ziad Ismaili Alaoui's user avatar
0 votes
0 answers
54 views

The formal proof that one Turing Machine computes one specific function

I have asked one similar question QA_1 "The formal proof that one Turing Machine recognizes one specific language" and the answer fills the part "It does not generate any string that is ...
An5Drama's user avatar
  • 203
0 votes
1 answer
60 views

Wrapping one's head around priority arguments

One of my undergraduate math professors used to say "we'll always be drawing a picture, even when it is impossible", and I came to strongly sympathize with his witty point. Some recursion ...
P. Trinli's user avatar
  • 101
0 votes
1 answer
63 views

The formal proof that one Turing Machine recognizes one specific language

When given one grammar, we can formally prove that it can recognize one language using QA_1 Since Kleene's Theorem gives the equivalence between the regular grammar and the NFA, we can also use QA_1 ...
An5Drama's user avatar
  • 203
0 votes
2 answers
110 views

Distinct edge weights assumption in second best MST algorithms only replacing 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
1 vote
1 answer
83 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
34 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
92 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 ...
entangled_photon's user avatar
-1 votes
2 answers
259 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
35 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,654
1 vote
2 answers
211 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
92 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
250 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
35 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
562 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
93 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
57 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, ...
Julius Hamilton's user avatar
2 votes
0 answers
50 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
  • 1,014
1 vote
0 answers
34 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
39 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
91 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
125 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
197 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
49 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
36 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
1 vote
2 answers
426 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
242 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
72 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
  • 976
-4 votes
5 answers
428 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
274 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
284 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
2 3 4 5
14