On Computational Complexity of Computing Jones Polynomials
论计算琼斯多项式的计算复杂度
基本信息
- 批准号:17500014
- 负责人:
- 金额:$ 2.2万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for Scientific Research (C)
- 财政年份:2005
- 资助国家:日本
- 起止时间:2005 至 2007
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Knot theory is a subfield of topology. A knot is a simple (non-self-intersecting) closed curve embedded in R^3. More generally, one may study links. A link is a finite collection of disjointly embedded knots. Works on knot theory have led to many important advances in other areas, biology, chemistry and physics. For classifying and characterizing links, various invariants have been defined and profoundly studied in knot theory. The Jones polynomial is a useful invariant. It is known that computing the Jones polynomial is generally #P-hard. It is expected to require exponential time in the worst case. Recently, it has been recognized that it is important to compute Jones polynomials for links with reasonable restrictions.EIn this project, we showed that Jones polynomials of pretzel links are computable in O(n^2) time, where n is the number of the edges in the input Tait graph. Moreover, we propose a fast algorithm for computing Jones polynomials of Montesinos links. Given the Tait graph of a Montesinos diagram with n edges, our algorithm runs with O(n) additions and multiplications in polynomials of degree O(n), namely in O(n^2log {n}) time.
纽结理论是拓扑学的一个子领域。纽结是嵌入R^3中的简单(非自相交)闭合曲线。一般来说,可以研究链接。链接是不相交嵌入的结的有限集合。关于纽结理论的研究在生物学、化学和物理学等其他领域取得了许多重要进展。纽结理论中定义了各种不变量,并对它们进行了深入的研究。琼斯多项式是一个有用的不变量。众所周知,计算琼斯多项式通常是P-困难的。预计在最坏情况下需要指数时间。最近,人们已经认识到,它是重要的,以合理的限制,计算琼斯多项式的链接。在这个项目中,我们表明,琼斯多项式的pretzel链接是可计算的O(n^2)时间,其中n是在输入Tait图的边的数量。此外,我们提出了一个快速算法计算Montesinos链路的琼斯多项式。给定具有n条边的Montesinos图的Tait图,我们的算法在O(n)次多项式中运行O(n)次加法和乘法,即在O(n^2log {n})时间内运行。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Extraction of temporal relation by the creation of historical natural disaster archive.
通过创建历史自然灾害档案提取时间关系。
- DOI:
- 发表时间:2006
- 期刊:
- 影响因子:0
- 作者:S.;Yoshioka;S.;Tani;S.;Toda
- 通讯作者:Toda
Fast algorithms for computing Jones polynomials of certain links
- DOI:10.1016/j.tcs.2006.11.012
- 发表时间:2007-04
- 期刊:
- 影响因子:0
- 作者:Masahiko Murakami;Masao Hara;Makoto Yamamoto;Sei'ichi Tani
- 通讯作者:Masahiko Murakami;Masao Hara;Makoto Yamamoto;Sei'ichi Tani
新聞記事コーパスにおける自然災害の特性と時間関係の抽出
从报纸文章语料库中提取自然灾害的特征和时间关系
- DOI:
- 发表时间:2006
- 期刊:
- 影响因子:0
- 作者:吉岡 卓;谷 聖一;戸田 誠之助
- 通讯作者:戸田 誠之助
Kolmogorov記述量に基づく類似度距離による方言自動分類の試行
基于柯尔莫哥洛夫描述量的相似距离自动方言分类试验
- DOI:
- 发表时间:2007
- 期刊:
- 影响因子:0
- 作者:田中 ゆかり;谷 聖一
- 通讯作者:谷 聖一
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
TANI Seiichi其他文献
TANI Seiichi的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('TANI Seiichi', 18)}}的其他基金
On computational complexity of computing polynomial invariants of links
计算链路多项式不变量的计算复杂度
- 批准号:
14580391 - 财政年份:2002
- 资助金额:
$ 2.2万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
相似海外基金
The Jones Polynomial and Hyperbolic Geometry of Surfaces
曲面的琼斯多项式和双曲几何
- 批准号:
2203255 - 财政年份:2022
- 资助金额:
$ 2.2万 - 项目类别:
Continuing Grant
The Geometry and Topology of the Jones Polynomial
琼斯多项式的几何和拓扑
- 批准号:
1811114 - 财政年份:2018
- 资助金额:
$ 2.2万 - 项目类别:
Continuing Grant
The Geometry, Topology and Number Theory of the Jones Polynomial
琼斯多项式的几何、拓扑和数论
- 批准号:
1406419 - 财政年份:2014
- 资助金额:
$ 2.2万 - 项目类别:
Standard Grant
The Geometry, Topology, Asymptotics and Number Theory of the Jones Polynomial
琼斯多项式的几何、拓扑、渐近和数论
- 批准号:
1105678 - 财政年份:2011
- 资助金额:
$ 2.2万 - 项目类别:
Standard Grant
The Geometry, Topology and Asymptotics of the Jones Polynomial
琼斯多项式的几何、拓扑和渐近
- 批准号:
0805078 - 财政年份:2008
- 资助金额:
$ 2.2万 - 项目类别:
Continuing Grant
The Geometry and Topology of the Jones Polynomial
琼斯多项式的几何和拓扑
- 批准号:
0505445 - 财政年份:2005
- 资助金额:
$ 2.2万 - 项目类别:
Continuing Grant