The theory of Grobner bases has garnered the interests of a large number of researchers in computational algebra due to its applications not only in mathematics but also in areas like control systems, robotics, cryptography to name a few. It is well known that the computation of Grobner bases takes time doubly exponential in the number of indeterminates rendering it impractical in all but a few places.The current known algorithms for Grobner bases depend on the term order over which Grobner bases is computed. In this thesis, we study computational complexity of some problems in computational ideal theory. We also study the algebraic formulation of combinatorial optimization problems. Gritzmann and Sturmfels (1993) posed the following question: Given a set of generators, decide whether it is a Gr¨obner bases with respect to some term order. This problem, termed as the Grobner Basis Detection(GBD)problem, was introduced as an application of Minkowski addition of polytopes. It was shown by Sturmfels and Wiegelmann (1997) that GBD is NP-hard. We study the problem for the case of zero-dimensional ideals and show that the problem is hard even in this special case. We study the detection problem in the case of border bases which are an alternative to Grobner bases in the case of zero dimensional ideals. We propose the Border Basis Detection(BBD) problem which is defined as follows: Given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. It is shown that BBD is NP-complete. We also formulate the rainbow connectivity problem as a system of polynomial equations such that solving the polynomial system yields a solution to it. We give an alternate formulation of the rainbow connectivity problem as a membership problem in polynomial ideals.

隨網際網路、行動載具及數位科技之進步，金融服務之提供不再受限於地域上之隔閡。邇來，有許多國際性投資銀行擬透過其所經營之網路交易平台向我國投資人提供證券經紀服務，然因我國現今並未開放外國證券商得跨境提供我國投資人證券經紀服務，在相關規範上付之闕如。 然而，法律上之禁止並無法阻止科技進步興起之跨境證券活動浪潮。如有朝一日我國擬開放外國證券商跨境提供我國投資人證券經紀等金融服務時，應採取何種規範方式及相關規範內容為何，有其討論之需要性及必要性。 按此，本文首先將介紹我國現行證券商相關之規範制度，後參酌美國、澳洲及德國對於外國證券商跨境提供其國內投資人證券經紀服務之規範方式及內容，輔以國際證券管理機構組織所歸納使用於跨境證券活動之三種規範制度，嘗試提出我國對外國證券商跨境提供我國投資人證券經紀服務得採行之規範方式及內容之建議。 本文研究結果建議，我國應針對不同身分別之投資人分別採用國民待遇規範制度及認可規範制度。即在非屬專業投資人部分，採用國民待遇規範制度；而在專業投資人部分，採用認可規範制度。同時，建議就有關跨境提供證券經紀服務之開放可分階段進行。最後，針對我國現行證交法及其相關規定，本文亦參考美國、澳洲及德國在相關規範架構下之細部規定，提出法規修正之建議及我國可能可以考慮之細部規範內容。 在跨境金融服務興起的今日，重新思考及架構一套符合證券及金融市場國際化之規範架構及方式是一個必經的歷程，希望透過本文之研究結果及建議，能幫助我國在此波金融國際化之浪潮中立足國際。 / With the progress of the Internet, mobile vehicles and digital technology, the provision of financial service is no longer limited to geographical barriers. Recently, there are a lots of international investment banks intend to provide securities brokerage services to our domestic investors through their electronic trading platform. However, since Taiwan is not yet open to foreign securities firms to provide securities brokerage service to our domestic investors on a cross-border basis, there is lack of any relevant regulation. Nonetheless, the legal prohibition on the provision of service on a cross-border basis can not stem the tide of the cross-border securities activities resulted by the technological advancement. If one day Taiwan opens the foreign securities firms to provide securities brokerage services and/ or other financial services to our domestic investors on a cross-border basis, it is necessary and a must for Taiwan to consider what regulatory model and what regulations should be taken. Given the above, this study will first introduce the current regulatory regime related to the securities firms in Taiwan, and then take the regulatory regime and regulations governing the foreign securities firms providing securities brokerage service to the domestic investors on a cross-border basis adopted by the US, Australia and Germany and the three types of regulatory regimes summed up by the IOSCO, which are used for the regulation of cross-border securities activities, into account to try to propose the suggestions on the possible regulatory regime and regulations for Taiwan to adopt for this issue. The results of this study suggest that Taiwan should adopt the regulatory tools called National Treatment and Recognition and used them depend on the type of investor. That is, as to the non-professional investor, Taiwan should adopt National Treatment to regulate the cross-border securities brokerage service; and as to the professional investor, Taiwan should adopt Recognition to regulate the same. At the same time, this study suggests the cross- border provision of securities brokerage service could be considered to be opened by phases. Finally, as to the current Taiwan Securities and Exchange Act and its relevant regulations, this study also provide the proposed amendments and the relevant details by making reference to the regulations adopted by the US, Australia and Germany under the regulatory regime of each of them. In today’s world, it is a must to rethink and structure a regulatory regime and regulations that conform to the internationalization of securities and financial markets. It is hopeful that the results and suggestions in this study could assist Taiwan to gain a footing in the arena of the international financial market.

Le but de cette thèse est de calculer l'optimum d'un polynôme sur un ensemble semi-algébrique et les points où cet optimum est atteint. Pour atteindre cet objectif, nous combinons des méthodes de base de bord avec la hiérarchie de relaxation convexe de Lasserre afin de réduire la taille des matrices de moments dans les problèmes de programmation semi-définie positive (SDP). Afin de vérifier si le minimum est atteint, nous apportons un nouveau critère pour vérifier l'extension plate de Curto Fialkow utilisant des bases orthogonales. En combinant ces nouveaux résultats, nous fournissons un nouvel algorithme qui calcule l'optimum et les points minimiseurs. Nous décrivons plusieurs expérimentations et des applications dans différents domaines qui prouvent la performance de l'algorithme. Au niveau théorique nous prouvons aussi la convergence finie d'une hiérarchie SDP construite à partir d'un idéal de Karush-Kuhn-Tucker et ses conséquences dans des cas particuliers. Nous étudions aussi le cas particulier où les minimiseurs ne sont pas des points de KKT en utilisant la variété de Fritz-John. / The objective of this thesis is to compute the optimum of a polynomial on a closed basic semialgebraic set and the points where this optimum is reached. To achieve this goal we combine border basis method with Lasserre's hierarchy in order to reduce the size of the moment matrices in the SemiDefinite Programming (SDP) problems. In order to verify if the minimum is reached we describe a new criterion to verify the flat extension condition using border basis. Combining these new results we provide a new algorithm which computes the optimum and the minimizers points. We show several experimentations and some applications in different domains which prove the perfomance of the algorithm. Theorethically we also prove the finite convergence of a SDP hierarchie contructed from a Karush-Kuhn-Tucker ideal and its consequences in particular cases. We also solve the particular case where the minimizers are not KKT points using Fritz-John Variety.