# All Questions

11,368 questions
Filter by
Sorted by
Tagged with
1answer
63 views

### Proving NP-complete problem

Suppose the following problem: Given an undirected graph G=(V,E), is it possible to choose a subset V' of vertex set V, such that deleting it removes all triangles (cycles of length 3), where |V'| is ...
1answer
271 views

1answer
1k views

### why is a Turing machine defined as a 5-tuple? [closed]

[Edited to provide better context.] In a comment on meta, JɛﬀE suggested that this would be a good topic for a question to ask here. why is a Turing machine defined as a 5-tuple?
1answer
623 views

### Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?
1answer
256 views

### Does a Non deterministic TM halt after the same number of steps on the same input? [closed]

Let $M$ be a Turing Machine (TM) which decides a certain language. Enter an input $x$ to $M$ and let the machine compute on $x$. After some time, $M$ will halt. If $M$ is a deterministic TM, it will ...
1answer
382 views

### Theoretical Computer Science or Sensor Networks

I am a first year PhD student in computer science. The major areas my supervisor is working with are: Theoretical Computer Science (knowledge representation, uncertainty, etc.) and wireless sensor ...
1answer
3k views

### Proof that DFA that accepts string has NFA that accepts reversal of string

I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string ...
1answer
1k views

### Alternative Turing Machine Proofs

I am asking this question again. I am aware of, and have read the other similar "alternative proof TM" questions, but unfortunately, they do help me. I am looking for a TM Halting Problem proof that ...
1answer
76 views

### We know that X3C is NP-complete with |X|=3q and |C|=m. Is this problem still remains NP-complete if |C|<2q? [closed]

Exact-Cover-by-3Sets (X3C) is NP-complete. If the number of classes i.e. |C|<2q then whether this is version of X3C is NP-complete or not?
2answers
4k views

### Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
1answer
745 views

### Self-avoiding walk in Graph [closed]

Short question: How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$? Long question: Edit: This question is not about p = np. I am searching for a way to calculate the numbers ...
1answer
314 views

### whats the difference between nondeterminism and parallelism? [closed]

pondering another Q/A & the responses on here leads to this question: whats the difference between nondeterminism and parallelism? am aware of basic answers. have some of my own ideas on ...
2answers
981 views

### Proof of correctness of in-place Quick sort

I have found proof of correctness of Quick sort (not in-place version), Please refer me a proof of correctness of in-place Quick sort, or provide proof here is very appropriated. a typical ...
2answers
659 views

### Is halting that hard? [Yes] [closed]

I want to make a modification to the halting problem. The output now has two possibilities: This program halts and it does not have the crossing structure (defined below); This program does not halt ...
1answer
990 views

### Polynomial time algorithm to solve the TSP on an m by n solid grid

Is there a polynomial algorithm to solve TSP (or Ham Cycle) on an m by n solid grid graph whose points are at unit distance apart? I've heard about Umans and Lenhart research paper but reading such ...
2answers
199 views

### A sandwich Algorithm / Data Structure [closed]

$O(n^c)$ is asymptotically greater than $O(\log^d n)$ for all possible pair of values of $c$ and $d$. Can you give an example of a problem (or data structure) which has running time (or query/...
1answer
126 views

### NP hard? Maximize the average for a subset of numbers

Given a set of real numbers, choose a subset to maximize the average subject to the average not exceeding a given threshold. Is it NP hard? I think so, but I cannot come out with a proof. Thanks a ...
1answer
143 views

### Are there proofs which show that AIs are bound to be “worse” than the human brain? [closed]

I was talking with two PhDs (both teach IT related subjects) about artificial intelligence the other day. They were in agreement that an AI can never reach the level of the human brain, but failed to ...
1answer
148 views

### Do irrational number contain infinate/every patterns of sequences? [closed]

I guess the question is "does an 'infinite' number of patterns imply 'every' number of patterns?" For instance, if you could quickly calculate the decimal sequence of π, could you not (in ...
2answers
1k views

### Deterministic CFL closure Property Homomorphism [closed]

I tried to research the following question with no results: Can you find one example where the following holds true: Let L = {xxxxxxx} be a deterministic-context-free Language and Let h(...) = xxxxx ...
1answer
23 views

### Help find algorithm for array-based task

Given array if numbers a[1..n]. Pair of numbers (i, j) is interesting, if i < j и a[i] > 2a[j]. How to count number of interesting pairs in O(nlogn)? What is the solution? My solution is not ...
1answer
120 views

### Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
1answer
26 views

### Polynomial-time reducibility of Primality and 3-SAT

Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated. Thank you.
1answer
374 views

### Does any DAG can be topologically sorted? [closed]

I am not good enough in computer science. My intention is to solve some programming problem in terms of DAG's. The key point is that before getting them into database, I need run "topological sort" in ...
1answer
160 views

### Dance Partner Problem NP-completeness [closed]

I really can't think of a concise way to phrase this problem, which makes it hard to search for, so forgive me if this is a duplicate question. I've come across a problem and I would like to know if ...
1answer
129 views

### non deterministic algorithm always find the right solution? [closed]

i'm confused since i see some books mention the NP time algorithms as "very lucky" that means it always finds the right path? also can someone explain the coming points to me please... A ...
1answer
130 views

### A simple challenge

Consider the following problem: given a number $n$, an alphabet $\Sigma$, and a finite language $L$, how many strings of length $n$ in $\Sigma^*$ contain at least one word $w\in L$? E.g. ...
1answer
241 views

### Some questions (still) unresolved about braids?

I was looking for interesting questions pertaining to braid theory. I don't know if the following are considered important, but I'd like to ask: (1) in relation with the following link, is it true ...
1answer
251 views

### Can on every instance P = NP? [closed]

I want to ask a question concerning some aspects of the P vs. NP problem. NOTE: Possibly by "popular" standards i am a crank (i tend towards P=NP), but lets focus on the issue (please with a grain of ...
2answers
691 views

### open problems on $NP$-complete? [closed]

How can we find the list of open problems on $NP$-comlpete?
1answer
332 views

### Attacking TSP via small nonintersecting circuits

Consider the problem of finding smaller "non-intersecting" circuits or paths in graphs embedded in the euclidean plane (visiting all vertices) in the sense of geometric intersections of edges plotted ...
3answers
372 views

### How can I call functions that are not “first-class functions”?

I mean, is there an antonym for "first-class function"?
5answers
27k views

### Application of calculus in computer science

Where are derivatives and integrals used in the field of Computer Science? What are their applications?
1answer
356 views

### What function has the signature $A \times \left ( B + C \right ) \rightarrow \left ( A \times B \right ) + \left ( A \times C \right )$?

$A \times \left ( B + C \right )$ is isomorphic to $\left ( A \times B \right ) + \left ( A \times C \right )$, right? That means there's a function from one to the other and another function back....
1answer
207 views

### Is the sub-bit model of quantum computation equivalent to other models? [closed]

In a comment to this question Peter Shor asked me for a reference about the third described in the question point of view, namely, that quantum computers can be described as computers that can ...

15 30 50 per page