# 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.

576 questions
Filter by
Sorted by
Tagged with
344 views

### Show that C(n) = {a^k | k is a multiple of n} is a regular language

I came across this question in an exam book and was unable to find a solution: Prove that C(n) = {a^k | k is a multiple of n} is a regular language for every natural number n ≥ 1. I wasn't able to ...
76 views

### Definition of InLeft and InRight

So in reading I have come across the terms "InLeft" and "InRight" and I am unable to find a concrete definition for it. I have found it used in the specification for COQ, and in some notes on ...
171 views

### Find the loop invariant of the given while loop

I don't know how to find a loop invariant. I'm not sure where to start. Can anyone find the loop invariant of the given program and explain your method please. ...
300 views

### Can't Understand this Subset Construction Proof

This proof is from Introduction to Automata Theory Languages and Computation by Hopcroft & Ullman and is regarding a 'bad case' for subset construction. The NFA which is being converted is as ...
427 views

### Accounting method vs Potential method for analysing an augmented stack and differences with standard complexity analysis

With reference to chapter 17 of CLRS, (Amortized analysis). I'm trying to understand the differences between the accounting method and the potential method. Let's start with standard analysis of the ...
66 views

### Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree

I'm trying to write an induction statement to prove a full node in a tree but I have no idea how to do that. I've always been terrible when it comes to logic. Where do I even start with this? I know ...
589 views

### Proving correctness of an iterative Fibonacci algorithm

One of the questions in the problem sets that I'm struggling in is this specific number that asks me to prove an iterative Fibonacci algorithm. The algorithm is written below: ...
891 views

### Prove that Big-O is transitive by relation. What does it mean by 'by relation'?

Prove $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$. The question is Prove that Big-O is transitive by relation. What does it mean by ...
If we take a look at Gödel's paper “On formally undecidable propositions”, the first self referential proof given in the paper, with the following formula: $$n \in K \equiv \overline{\textit{Bew}}[R(... 0answers 47 views ### How can I prove impossibility of generalizing a given higher order function from pure to monadic or applicative? There is a great divide in Haskell between pure and monadic algorithms. While the latter are indistinguishable from their usual imperative counterparts, the former can get much more magical. What this ... 0answers 34 views ### How to prove that for a decidable problem the problem and the compliment of the problem are semi-decidable? Given a decidable problem, how would I go about proofing that the problem and the complement of the problem have to be semi-decidable? 0answers 2k views ### proof why worst case for bubble sort is array sorted in reverse order Question 1: Let's say we have bubble sort algorithm which sorts numbers in ascending order. Intuitively one might agree that the worst case input for this algorithm is array already sorted in ... 0answers 117 views ### Doubt on dovetailing Let < M > be an encoding of a Turing machine. L = { < M > | M is a Turing machine that accepts a string of length 2014 } Above language is R.E(even though we have infinite TM's) as we have ... 2answers 218 views ### Why and how geometric series are used for proofs? I often see that someone uses geometric series for proofs related to time complexity, but also I can't understand why they are used. Are they making proving easier? And how can I use this 'tool' for ... 1answer 285 views ### Lower bound of complexity of simple problem Consider the simple problem: Given a list of objects L of length n, and an object O, determine if O is in L. It is intuitive that there cannot exist an algorithm a with worst-case time complexity ... 1answer 330 views ### Proving worst-case running time is in \Omega(n^2) I was given the following method to argue that an algorithm A has a worst-case running time of \Omega(n^2): We need to argue that there exists an input x of size n, the running time of A... 2answers 368 views ### Naive argument that P ≠ NP Consider the following naïve argument that any algorithm solving SAT must take \Omega(2^n) time in the worst-case scenario. Let f(x_1,x_2,\dots,x_n) be a Boolean function in conjunctive normal ... 1answer 53 views ### Proof that if a function is computable with standard programs it is computable with Turing Machines Where can i find a proof related to the subject mentioned? 1answer 57 views ### On clarification of intersection of classes definition How do you define \oplus P\cap PP? L\in\oplus P iff \exists\mbox{ NTM }M:\forall x,\#acc_M(x)\mod2\equiv0. L\in PP iff \exists\mbox{ NTM }M:\forall x,\#acc_M(x)>\#rej_M(x). Consider ... 1answer 425 views ### Mathematical proofs implemented purely by Lambda Calculus I've seen often stated that Lambda Calculus can be used for mathematical proofing but I haven't yet seen any example how it is actually used for the task. Is there a simple example, lambda ... 0answers 74 views ### How to prove QUADPROG is NP-hard using 3COLOR? [duplicate] I am given a task to prove using 3COLOR that Quadratic Programming is NP-hard. Does anyone have a clue on how this is meant to be done? 2answers 167 views ### Computational Complexity and P vs. NP, A New Insight [closed] There is a preprint on arXiv that states (in my own words). If there are three numbers (digits) and task is to add all three numbers. First we well take two number to add, set aside third number. ... 1answer 76 views ### Proving or disproving a set of total functions is countable Let S be the set of total functions from N \rightarrow M, such that for each f \in S, there is i > 1 such that for all j < i, f(i) and f(j) are not equivalent Turing machines. ... 1answer 323 views ### Must algorithm for comparing numbers investigate all bits? Suppose algorithm A on a digital computer takes as input integers x and y in binary. The algorithm outputs one if x=y, and zero if x \neq y. Is there a proof that for any input x and y ... 2answers 85 views ### Why algorithms calculating non-tirivial zeros can't be used as proofs of Riemann Hypothesis? Recently I was reading again this propositions as types paper by Philip Wadler: http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf It gives an impression, ... 0answers 280 views ### Need Help Understanding Proof by Contradiction for Halting Problem I understand what the halting problem describes, but I do not understand how the proof by contradiction associated with it proves that it is impossible to solve. The proof by contradiction can be ... 0answers 74 views ### Inductive proof that n^2 + bn + d is O(n^2) using definition of big O Given that T(n) = n^2 + bn + d then it's O(n^2) if I can prove that: O(n^2) = \{T(n): \text{there exist positive constants } c, n_0 \text{ such that } \forall n \geq n_0, 0 \leq T(n) \leq cn^2 \}... 2answers 98 views ### Element wise product sum of two arrays I have two arrays, namely a and b. Both have the same length n. I have to find the maximum value of \sum a_i b_j, in which every element can be used at most one time. My algorithm for solving ... 0answers 698 views ### Expectation for the number of comparisons in a randomized Quicksort I found this link: http://theory.stanford.edu/~tim/w11/l/qsort.pdf and it kind of theoretically describes how to approach finding expectation for the number of comparisons in a Quicksort. Using ... 3answers 96 views ### When is the empty word part of A^+? My professor mentioned the below statement in class but without a proof. I am trying to prove it for myself as I don't understand 100% why this is always the case. Given is A, a subset of {0,1}^*. ... 1answer 92 views ### Could the execution of a Haskell program be considered as a proof using equational reasoning Could the execution of a Haskell program be considered as a proof in equational reasoning. This follows on from my earlier question on Haskell and inductive proof. Currently I am stuck between morally ... 1answer 448 views ### Does a Haskell program count as an inductive proof? Is the following statement from  true? "Since recursion is the main computational technique, a terminating pure Haskell program counts as an inductive proof of a theorem." My intuition is that ... 1answer 71 views ### How do you prove that the set of decimal representation of the 4 divisble natural numbers is regular? This is from an old exam, the last Task no one could solve correctly and I'm curious how it's done :p Show that the set of decimal representation (without leading zeroes) of the divisible numbers by <... 1answer 833 views ### Proof of correctness of algorithm Can someone help me prove the correctness of this algorithm: ... 2answers 105 views ### Is 2^n steps enough to tell if DTM will run forever? In the space hierarchy theorem proof for PSPACE from Wikipedia, we reject the input after 2^{|f(x)|} steps on the machine M, reportedly to avoid infinite running time. My question is: how is it ... 1answer 6k views ### Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma [duplicate] Question: L is a language defined as \ L = \{1^l | l\in primes\} (strings of 1s having a prime length). Show that this is not a regular language (\ L \notin REG). You may either use the theory ... 4answers 683 views ### Is it necessary to learn how to prove Mathematical theorems as a CS Student? [closed] I've just started my undergraduate course and have tried my hands on MIT's OpenCourseWare on Discrete Math on Logic and Proofs. There was a particular question asking to prove Cantor's Theorem: ... 0answers 511 views ### Proving a greedy algorithm Hey so I'm studying for a midterm and I've run into this problem in the material. I'm not sure how to go about solving it. If I use regular induction in part a, I get something a bit tautological. Any ... 1answer 217 views ### Proving that  (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*? How would I prove that these two regexes are equal to one another?$$ (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$$I'm permitted to use the following regular expression identities. 2answers 338 views ### Proving that a sentence in first-order logic is not valid By the completeness of FOL, one can show that a sentence S in FOL is valid, i.e. that it holds true in every model, by exhibiting a proof of S. Such a proof string is a certificate of the validity ... 1answer 180 views ### Basic approximation algorithms understanding Question: Suppose we have 2 algorithms Alg1 and Alg2 for the same minimization problem. We know that Alg1 is a 2-approximation algorithm and Alg2 a 4-approximation algorithm. Is the ... 1answer 301 views ### The Church-Turing-Thesis in proofs Currently I'm trying to understand a proof of the statement: "A language is semi-decidable if and only if some enumerator enumerates it." that we did in my lecture. One direction of the proof goes ... 1answer 453 views ### Construction of the complement of universal Turing machine - where is the catch? This is pretty fundamental but I'm getting confused. Let U be the Universal Turing Machine and L_{u} the language it accepts which is recursively enumerable. Obviously we are not able to construct ... 1answer 396 views ### A confusion about the Reduction via Computation History [Updates: Thanks for @Raphael 's notification, I delete the screenshot of the book and type the LaTex materials] In Sisper's Intro to the theory of Computation, there is a reduction method via ... 0answers 69 views ### Does a given Turing machine works in time limited by 5n? There doesn't exist an algorithm which decides on the following problem: Does a given Turing machine work in time limited by 5n? n is the length of w. w is an input word. The answer is: No, ... 1answer 101 views ### how to prove original intervals and canonical form of intervals have the same interval graph According to this paper,a family of intervals is said to be canonical if the coordinates of the endpoints of the intervals are distinct integers between 1 and 2n where n is the number of intervals. ... 2answers 390 views ### Why does this not prove P\neq NP? Fiorini, Massar, Pokutta, Tiwary and De Wolf (Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Journal of the ACM 62(2):article 17, 2015; PDF, ArXiv) show any linear program that ... 1answer 83 views ### Randomized BST height analysis : How Z_{n,i} and Y_{k-1} are independent? I am referring to this video https://www.youtube.com/watch?v=vgELyZ9LXX4 at 1:08:39 . n : number of nodes in the tree Z_{n,k} : Indicator random variable that activates when rank of the root ... 2answers 1k views ### What exactly is going on in a proof by induction of a recurrence relation? In CLRS, it works through an example going through a recurrence relation proof using the "substitution method". We have the recurrence$$T(n) = 2T(\lfloor n/2 \rfloor) + n \ \ \ \ \ \ \ \ \ \ \ \ \ ...
Statements of the PCP theorem always speak of a proof of length $poly(n)$. But what polynomial is that exactly? Could you actually construct the PCP for some mathematical fact in real life?