We’re rewarding the question askers & reputations are being recalculated! Read more.

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
2
votes
1answer
390 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: ...
0
votes
1answer
629 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 ...
5
votes
1answer
196 views

Analogy between Gödel's incompleteness proof and Richard's argument

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(...
1
vote
0answers
45 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 ...
0
votes
0answers
31 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?
0
votes
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 ...
1
vote
0answers
99 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 ...
0
votes
2answers
183 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 ...
0
votes
1answer
259 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 ...
2
votes
1answer
203 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$...
1
vote
2answers
345 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 ...
1
vote
1answer
49 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?
0
votes
1answer
56 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 ...
5
votes
1answer
364 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 ...
0
votes
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?
0
votes
2answers
164 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. ...
2
votes
1answer
64 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. ...
-1
votes
1answer
305 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$ ...
3
votes
2answers
80 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, ...
0
votes
0answers
241 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 ...
0
votes
0answers
56 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 \}$...
1
vote
2answers
64 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 ...
0
votes
0answers
567 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 ...
2
votes
3answers
87 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}$^*$. ...
0
votes
1answer
84 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 ...
3
votes
1answer
372 views

Does a Haskell program count as an inductive proof?

Is the following statement from [1] 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 ...
2
votes
1answer
69 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 <...
0
votes
1answer
630 views

Proof of correctness of algorithm

Can someone help me prove the correctness of this algorithm: ...
1
vote
2answers
102 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 ...
2
votes
1answer
3k 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 ...
2
votes
4answers
337 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: ...
0
votes
0answers
495 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 ...
1
vote
1answer
197 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.
2
votes
2answers
270 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 ...
1
vote
1answer
127 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 ...
3
votes
1answer
276 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 ...
3
votes
1answer
328 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 ...
2
votes
1answer
277 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 ...
0
votes
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, ...
2
votes
1answer
79 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. ...
5
votes
2answers
362 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 ...
2
votes
1answer
66 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 ...
2
votes
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 \ \ \ \ \ \ \ \ \ \ \ \ \ ...
1
vote
0answers
34 views

What's the polynomial involved in the PCP theorem?

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?
0
votes
0answers
74 views

How to prove that a stack is equivalent to a queue with reversed inputs

Say I push the values 1,2,3,4 onto a stack. Then popping them, they will come back in the order 4,3,2,1. If I push the values 1,2,3,4 onto a queue then removing from a queue results in 1,2,3,4. ...
0
votes
0answers
94 views

How to prove for string of triplets that it is a Regular Language? [duplicate]

Let Σ2 = {0, 1}, and define Σ = Σ23. Informally, Σ* is the set of triples of the form (a, b, c) where a, b, c are single binary digits. Consider a string s ∈ Σ* : it is a sequence of such triples. ...
1
vote
1answer
101 views

Language of CFG: $S \to aS | aSbS | \varepsilon$

I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of $w$ has at least as many $a$'s as $b$'s} \}$.I ...
3
votes
1answer
51 views

Prove $T$ is a BST iff for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$

Let $T$ be a complete binary tree. Prove that $T$ is a binary search tree if and only if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child ...
2
votes
1answer
88 views

Are all proof techniques which only look at black box behaviour of a TM relativizing?

I am currently working on a seminar on $\mathbf{P \stackrel{?}{=} NP}$ and one of the points I want to adress is the Relativization barrier. However, it is hard to find a concrete definition of a "...
7
votes
1answer
4k views

Proof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete)

I need to prove that TAUT is coNP-complete. I showed that $\text{TAUT} \in \text{coNP}$ by reducing $\text{SAT}$ to $\overline{\text{TAUT}}$. However, I cannot figure out how to prove that every ...