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

550 questions
Filter by
Sorted by
Tagged with
39 views

73 views

### Proving a first order logic theorem in equational logic with a term rewriting system

I am trying to translate and prove a theorem, originally written in first order logic (FOL), into a combination of equational logic (EL) and Boolean logic (BL) (more precisely a model of Boolean ...
21 views

### Can someone explain me the Credit-Debit proof method for calculating operations?

I've started taking a data structure course and we are currently learning about different data structures. We also learned when to increase the capacity of an array by creating another array with ...
21 views

### Proof by padding: $\textsf{TIME}(t_1(n)) = \textsf{TIME}(t_2(n)) \implies \textsf{TIME}(t_1(f(n))) = \textsf{TIME}(t_2(f(n)))$

I've been given the task of proving the statement in the title, which I found out it should be called the translational lemma by means of a padding argument; $f$, $t_1$ and $t_2$ are three ...
72 views

### Optimality of a Greedy Algorithm

If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you ...
23 views

### How to generate tests using Model-Based Testing paradigm (for a newcomer)

So I just learned of Model-Based Testing. It sounds like this is a practical approach to some level of formal verification of production software applications. As I understand it, you have a ...
66 views

### How was the four color theorem proved using brute-force search?

I recently learned some graph theory in Discrete Structures for Computer Science, we learned about the Four Color theorem, I realize there is a mathematical proof for this topic, but how was it ...
17 views

### Review of Formal Verification and How to Apply it to Greenfield Project [duplicate]

Last year I looked heavily into Formal Verification, such as automated theorem proving, model checking, type systems, symbolic evaluation, and many others. I probably spent a few weeks or maybe months ...
90 views

### What goes into proving two complicated programs are equivalent?

Say I wanted to prove that two programs were equivalent (either rigorously if possible, or informally if not). More specifically, say I have something relatively complex such as an HTTP server ...
40 views

### if a graph G(V,E) is connected $|E|\geq|V|-1$

If a graph G(V,E) is connected the number of edges is at least the number of Vertices-1. It is pretty evident if you think about it but how do i prove it formally?
37 views

### How to prove properties about a specific modular arithmetic equivalence

Ever since I was introduced to modular arithmetic, I've had some trouble with it. I think it uses a part of my brain that I haven't used often. Anyways, I've been thinking about this specific ...
67 views

### Show that a problem is NP-Complete

The problem is, K_longestPath: We are given a graph in which some of the vertices are "cities". No two cities have an edge between them, thus every city must be at distance at least 2 from each ...
66 views

### Deriving recursive definition from function specification

Given this function specification, where name xs is bound to a list, # denotes its cardinality and ...
120 views

### Uniqueness of solution in Arden's theorem

Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^*$ is the unique solution to $R=Q+RP$. The proof is reproduces below. My question is: What is the logical reasoning to prove ...
213 views

### Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)

Given undirected and connected graph $G = (V,E)$. Prove for any DFS run: for any $u,v \in V$ if $u.d>v.d$ then $u.d − v.d ≥ δ(u,v)$ $δ(u,v)$-distance of a shortest path (not necessarily unique) in ...
19 views

### Need clarification regarding certificates of coNP problems

NOTE: this is not an attempt to prove $NP \neq coNP$ There is one thing I have never been able to completely digest about the certificates of problems in $coNP$ and I would very much appreciate a ...
68 views

### Divide and Conquer a problem into a sub-problem to solve it efficiently

Assume that problem A cannot be solved in O(n^2) time. However, we can transform problem A into a problem B in O(n^2 log n) time, and then solve B, and finally transform the solution of B into the ...
44 views

### Is there a proof that “undetectable” malware cannot be written?

In Fred Cohen's paper "Computer Viruses - Theory and Experiments", he proves that for the general case, classifying malware is an undecidable problem. I was wondering whether there might be a ...
47 views

### On the complexity of existential and universal quantifiers

I'm trying to analyze the time complexities of the two former kind of quantifiers, I need help figuring out if I'm following the right path or if I'm making mistakes, here's what I've produced so far: ...
54 views

22 views

### Isn't ZKP is a reduction to a hard problem, rather than true zero knowledge?

Take for example "Hamiltonian cycle for a large graph". The proof works by starting with a graph G that contains a hamiltonian cycle, then constructing an isomorphic graph H, and then either showing ...
152 views

### Randomly built binary search trees

In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove: The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$. We define "...
142 views

### The law of excluded middle and decidability

I will divide my question in two parts. The first part I am sure that there is a objective answer, but I am not sure about the second part. First part: Is it all (decisions) problems trivial to prove ...
62 views

### It is decidable whether a pushdown automaton will accept a word? [duplicate]

I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable. I would say that you can simulate a push down automaton with a Turing Machine and, if it ...
3k views

### Show that there are infinitely more problems than we will ever be able to compute

I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ...
### Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)
We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...