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

575 questions
Filter by
Sorted by
Tagged with
533 views

### Proof-sketch on the language accepted by a Turing machine

Let $T$ be a Turing machine whose accepted language is $L(T)$. Let $X$ be another language. How do you approach a proof like $L(T)\subseteq X?$
2k views

### How to apply the pumping lemma to $\{0^m 1^n \mid 2n \leq m \leq 3n, m,n \geq 0 \}$?

I'm not really sure the how you would go about proving this language isn't regular with the pumping lemma: $L= \{0^m 1^n | 2n \leq m \leq 3n, m,n \geq 0 \}$ Does this indicate that $S = 2$, so we ...
345 views

### How do I explain that a polynomial time reduction is in fact polynomial time?

I have as an assignment question to show that $QuadSat=\{\langle\phi\rangle\mid\phi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$\}$ is $\sf NP$-Complete. My solution is as ...
218 views

### Proof of SAT is randomly reducible to UNIQUE-SAT

I am asking for help to explain some crucial points of the central lemma and it's proof of famous paper NP is as easy as detecting unique solutions by L.Valiant and V.Vazirani. The proof can be found ...
767 views

### Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we ...
1k views

### Convergence of Simulated Annealing Based Algorithms

I designed a simulated annealing-based optimization algorithm. My simulation shows that it converge fast. I am looking for some sort of proof to show that simulation annealing-based algorithm converge ...
226 views

572 views

### Proof by restriction: when is it valid to restrict to a special case?

I was reading a few notes on Proof by Restriction and I am confused: A Valid Proof by Restriction is the following: Directed Hamiltonian Cycle Problem is NP Complete because if we look only at ...
423 views

### Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?

I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem. Halting ...
73 views

### Progress of algorithms in problem spaces

Continuing in the vein of two prior questions (1) and (2), we started with sorting, where we had a set of $n!$ input possibilities a goal space of only one element consisting of the one correct ...
1k views

### k-Trees Graph Coloring

There is an exercise in Distributed Algorithm I have some difficulties to solve. There are few ideas, however nothing useful at the time. I will appreciate any help with it. Graph $G$ is a $k$-tree ...
163 views

### Proof of message complexity on the network

I try to provide a strict and mathematical rigorous proof to the following problem in Distributed Algorithms. Prove or make a contradiction: if to vertices $a$ and $b$ on the network $G$ are located ...
6k views

### How to show that given language is unambiguous

Given following grammar: \begin{align} S \rightarrow &A1B \\ A \rightarrow & 0A \mid \varepsilon \\ B \rightarrow & 0B \mid 1B \mid \varepsilon \\ \end{align} How can I show that ...
491 views

### Proving regularity via equivalence classes

Given two regular languages $L_1$ and $L_2$, we define a new language $$L=\{w_1w_2\mid \text{ there exist two words } x,y \text{ such that } xw_1\in L_1, w_2y\in L2\}$$ How do I show that $L$ is ...
112 views

### Lower bound on size of proof that a list of integers is sorted

Suppose we have a list of unbounded integers, written in binary, and we want to write a (formal) proof that the list is sorted in ascending order. Such a proof might look (informally) like: "2 < 3,...
93 views

### Proofs based on narrowing down sets of possibilities

Consider the argument made in this question based on the comparison sorting lower-bounds proof, which runs as follows. First, the comparison sorting lower-bounds proof was recited: For $n$ distinct ...
2k views

### How to show composition of one way function is not such?

I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function? Specifically: Say $f$ and ...
592 views

### How to determine the polynomial runtime of an NP reduction?

To show that a NP problem is NP-complete, we also have to show that $L \leq_{p} L'$ , where $L$ is proven NP-complete and you have to prove $L'$ also is. The thing I am confused is how in all NP-...
491 views

228 views

### The binary-GCD algorithm state machine [duplicate]

Possible Duplicate: Runtime of the binary-GCD state machine Hello I am doing self study from MIT OCW exercises and I could not understand this question. Can anyone explain me, First, why does ...
6k views

### Recurrence relation for time complexity $T(n) = T(n-1) + n^2$

I'm looking for a $\Theta$ approximation of $$T(n) = T(n-1) + cn^{2}$$ This is what I have so far:  \begin{align*} T(n-1)& = T(n-2) + c(n-1)^2\\ T(n) &= T(n-2) + c(n-1) + cn^2\\[1ex] T(n-2)...
280 views

### How to prove or disprove that f is computable?

If $f(x_1,\dots, x_n)$ is a total function that for some constant $K$, $f(x_1,\dots, x_n) \leq K$ for all $x_1,\dots, x_n$ then $f$ is computable. I want some hints on how to prove/disprove the ...
611 views

### If a predicate is not computable, what can be said about its negation?

Doing the following exercise: Let $\overline{HALT(x,y)}$ be defined as $\overline {HALT(x,y)} \iff \text{program number y never halts on input x}$ Show that it is not computable. Just want to make ...
1k views

### Rigorous proof against pseudo random function

I have the following problem: Deﬁne the keyed function F as follows: On input k ∈ {0, 1}$^n$ and x ∈ {0, 1}$^n$ , Fk(x) = k ⊕ x.Rigorously prove that F is not a pseudorandom function. How do I ...
2k views

### Providing Tight Example in Approximation Algorithm Analysis

Let's say I found a 2-approximation algorithm for a certain problem and I want to show that the analysis is tight. Do I now need to come up with an example of generic size $n$ or does it suffice to ...
14k views

### How do I write a proof using induction on the length of the input string?

In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ...
196 views

### Proving $\Omega(cf) = \Omega(f)$

I'm trying to prove the following lemma: $c$ is a positive real number and $f, g$ are functions from natural numbers to non-negative real numbers. I'm trying to prove rigorously that: $\Omega(cf(n))$...
2k views

I have this simple 'assignment' problem: We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike ...
1k views

### What approaches are most useful when proving uncomputability of a given function?

I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows: Reduction,...
2k views

### Proving a grammar only generates words whose alternating digit sums are multiples of three

This is homework and I'm looking for a push in the right direction. Proofs were never something I was properly taught, so now they're kind of a weak point. Here's the problem: The following ...
4k views

### How to show two models of computation are equivalent?

I'm seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea ...